back to table · edit · history · where entries came from · files · download
7511 bytes, as of the version from 2026-09-27 17:26 (current). Recorded here, not run.
"""Reproduce T342 channel capacities without writing to the website.
Run with SageMath and the numberdb package:
sage -pip install numberdb
sage -python generate.py --output entries.json
sage -python generate.py --verify
The first command is offline; --verify only reads the website. There is no
publication command. ChannelCapacities.value accepts other rational parameters.
The curated enumeration uses small halves, thirds and quarters and the
informative never-correct QSC limit, not a decimal or denominator-bounded
grid. Noiseless and input-independent capacities remain validation controls.
Closed forms are evaluated in Arb with 128 guard bits. The companion recovery
verification measures the retained accuracy and independently encloses matrix
capacity using MPFI primal/dual bounds. Exact cases are decided algebraically.
For QSC(3,1/3), the row entropy is log_2(3)-1/3, so capacity is exactly
1/3 bit, or log(2)/3 nats; both selected unit rows are retained.
"""
import argparse
import json
from pathlib import Path
import numberdb.sage as numberdb
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField
WORKING_GUARD = 128
DIGITS = 100
PARAMETERS = ('channel', 'shape', 'unit')
BSC_POINTS = ('1/4', '1/3')
Z_POINTS = ('1/4', '1/3', '1/2', '2/3', '3/4')
ALPHABETS = (3, 4, 8, 16)
BAC_POINTS = ('1/4,1/3', '1/4,1/2', '1/3,1/2')
def selected_parameters():
shapes = [('bsc', shape) for shape in BSC_POINTS]
shapes.extend(('z', shape) for shape in Z_POINTS)
for alphabet in ALPHABETS:
probabilities = ('1/4', '1/3', '1/2', '1')
shapes.extend(('qsc', '%s,%s' % (alphabet, probability))
for probability in probabilities)
shapes.extend(('bac', shape) for shape in BAC_POINTS)
for channel, shape in shapes:
for unit in ('nats', 'bits'):
yield dict(zip(PARAMETERS, (channel, shape, unit)))
def parse_parameters(params):
if set(params) != set(PARAMETERS):
raise ValueError('Expected channel, shape, unit')
channel, unit = params['channel'], params['unit']
if channel not in ('bsc', 'z', 'qsc', 'bac') or unit not in ('nats', 'bits'):
raise ValueError('Unknown channel or logarithmic unit')
shape = tuple(QQ(part.strip()) for part in params['shape'].split(','))
count = 2 if channel in ('qsc', 'bac') else 1
if len(shape) != count:
raise ValueError('Incorrect shape arity')
probabilities = shape
if channel == 'qsc':
alphabet = shape[0]
if alphabet.denominator() != 1 or alphabet < 2:
raise ValueError('Alphabet size must be an integer at least two')
probabilities = shape[1:]
if any(probability < 0 or probability > 1 for probability in probabilities):
raise ValueError('Probabilities must lie in [0,1]')
return channel, shape, unit
def entropy(probability, field):
if probability == 0 or probability == 1:
return field(0)
point = field(probability)
complement = field(1 - probability)
return -point * point.log() - complement * complement.log()
def logarithmic_capacity(ratio, unit, field):
ratio = QQ(ratio)
if ratio == 1:
return QQ(0)
if unit == 'bits' and ratio.denominator() == 1:
integer = int(ratio)
if integer > 0 and integer & (integer - 1) == 0:
return QQ(integer.bit_length() - 1)
result = field(ratio).log()
return result if unit == 'nats' else result / field(2).log()
def capacity(channel, shape, unit, field):
if channel == 'bsc':
probability = shape[0]
if probability == QQ(1) / 2:
return QQ(0)
if probability in (0, 1):
return logarithmic_capacity(2, unit, field)
result = field(2).log() - entropy(probability, field)
elif channel == 'z':
probability = shape[0]
if probability == 1:
return QQ(0)
if probability == 0:
return logarithmic_capacity(2, unit, field)
exponent = field(probability / (1 - probability)) * field(probability).log()
result = (1 + field(1 - probability) * exponent.exp()).log()
elif channel == 'qsc':
alphabet, probability = shape
if alphabet == 3 and probability == QQ(1) / 3:
return QQ(1) / 3 if unit == 'bits' else field(2).log() / 3
if probability == (alphabet - 1) / alphabet:
return QQ(0)
if probability == 0:
return logarithmic_capacity(alphabet, unit, field)
if probability == 1:
return logarithmic_capacity(alphabet / (alphabet - 1), unit, field)
result = (field(alphabet).log() - entropy(probability, field)
- field(probability) * field(alphabet - 1).log())
else:
first, second = shape
delta = 1 - first - second
if delta == 0:
return QQ(0)
if first == second:
return capacity('bsc', (first,), unit, field)
if first == 0 or second == 0:
return capacity('z', (first + second,), unit, field)
if first == 1 or second == 1:
return capacity('z', (2 - first - second,), unit, field)
first_entropy = entropy(first, field)
second_entropy = entropy(second, field)
slope = (first_entropy - second_entropy) / field(delta)
output_zero = 1 / (1 + slope.exp())
input_zero = (output_zero - field(second)) / field(delta)
if not (input_zero > 0 and input_zero < 1):
raise ArithmeticError('Insufficient precision to certify interior optimizer')
result = (entropy(output_zero, field) - input_zero * first_entropy
- (1 - input_zero) * second_entropy)
result = result if unit == 'nats' else result / field(2).log()
if not result.is_finite() or not result > 0:
raise ArithmeticError('Capacity enclosure is not finite and positive')
return result
class ChannelCapacities(numberdb.Generator):
table = 'T342'
parameters = PARAMETERS
type = 'R'
digits = DIGITS
rigour = 'proven'
def enumerate(self):
yield from selected_parameters()
def value(self, params, digits):
channel, shape, unit = parse_parameters(params)
field = RealBallField(numberdb.bits(digits, losing=WORKING_GUARD))
return capacity(channel, shape, unit, field)
def records():
from numberdb._generate import _check_precision, _check_rigour
from numberdb._write import to_text
generator = ChannelCapacities()
result = []
for params in generator.enumerate():
value = generator.value(params, DIGITS)
identity = ','.join(params.values())
_check_rigour(generator, generator.table, identity, value)
written = to_text(value, digits=DIGITS)
_check_precision(generator.table, identity, written, DIGITS, False)
result.append({'params': params, 'number': written})
return result
def main():
parser = argparse.ArgumentParser(description=__doc__)
mode = parser.add_mutually_exclusive_group(required=True)
mode.add_argument('--output', type=Path)
mode.add_argument('--verify', action='store_true')
args = parser.parse_args()
if args.verify:
report = ChannelCapacities().verify(sample=None)
print(report)
return 0 if report.ok else 1
args.output.write_text(json.dumps(records(), indent=2) + '\n')
return 0
if __name__ == '__main__':
raise SystemExit(main())