Capacity of the discrete memoryless channels - NumberDB

Capacity of the discrete memoryless channels

edit · history · discussion · files · long url · probability theory special values

Numbers

channel

shape

unit

$C$

binary symmetric channel $\operatorname{BSC}(p)$

1/4

nats:

0.1308120359411369591292018062337177104101177840068068346803407407347270979442620095493484891138803790

binary symmetric channel $\operatorname{BSC}(p)$

1/4

bits:

0.1887218755408671360903042079608623815698608057693607953418144909058236708457689218917103561885661816

binary symmetric channel $\operatorname{BSC}(p)$

1/3

nats:

0.05663301226513249096680829884110190881167633277767597179977234885149507673088222580282312351363239045

binary symmetric channel $\operatorname{BSC}(p)$

1/3

bits:

0.08170416594551048521292772271885015790685225897418560621091401212556843887230810414438619174857842458

binary Z-channel $Z(p)$

1/4

nats:

0.3869415302026467323604488393799814389457789880454991900534196875482603763608314709533749758526658222

binary Z-channel $Z(p)$

1/4

bits:

0.5582386267373454967866350791883892866153092518170761529868620351292157673858209231309150215487265215

binary Z-channel $Z(p)$

1/3

nats:

0.3256280644497098478740130007644762545225473553952299919620646360788499624083869008803191278817672287

binary Z-channel $Z(p)$

1/3

bits:

0.4697819937558681606722243248482857951058632879733485245021844956737714990489604787211774517078180111

binary Z-channel $Z(p)$

1/2

nats:

0.2231435513142097557662950903098345033746010855480072136712878724873917437682683334184072241003422357

binary Z-channel $Z(p)$

1/2

bits:

0.3219280948873623478703194294893901758648313930245806120547563958159347766086252158501397433593701551

binary Z-channel $Z(p)$

2/3

nats:

0.1381503384808171717434286137747800965074672570123436165526350715624985369417243315930175668948903642

binary Z-channel $Z(p)$

2/3

bits:

0.1993088082234066644449067673321048972695790985189374875000407584559760084753829659413988924863814584

binary Z-channel $Z(p)$

3/4

nats:

0.1002694531636751493081301751297276601964324280194145775713128285141542974046660563664268692479904909

binary Z-channel $Z(p)$

3/4

bits:

0.1446582428318823208165958756483484876864642947025674126216612595859552748375070573406773183368635828

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1/4

nats:

0.3629903489093150137529068913335227049632331738792372187641850625054793637007525819156350851820891084

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1/4

bits:

0.5236843762620233175440431519086788903296752134618418557975671454469218986401274844139908311066544237

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1/3

nats:

0.2310490601866484364724107071527255226918333781200850847068933364977978739898982385352877756654728958

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1/3

bits:

1/3

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1/2

nats:

0.05889151782819172726939705473526085253424035628236657055367431939740386026406689346482076431910405747

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1/2

bits:

0.08496250072115618145373894394781650875981440769248106045575265454109822779435856252228047491808824209

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1

nats:

0.4054651081081643819780131154643491365719904234624941976140143241441006712489142512677524278173134012

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

3, 1

bits:

0.5849625007211561814537389439478165087598144076924810604557526545410982277943585625222804749180882421

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1/4

nats:

0.5493061443340548456976226184612628523237452789113747258673471668187471466093044834368078774068660444

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1/4

bits:

0.7924812503605780907268694719739082543799072038462405302278763272705491138971792812611402374590441210

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1/3

nats:

0.3835760966023745699189586746584365753380129478636814086755542471323906009610406191174811989054737151

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1/3

bits:

0.5533833323717917580616814080695779883202474564100252527256631272785356962741885833036260334425490105

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1/2

nats:

0.1438410362258904637196095029969137157517548554488805282533328426746464753603902321690554495895526431

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1/2

bits:

0.2075187496394219092731305280260917456200927961537594697721236727294508861028207187388597625409558790

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1

nats:

0.2876820724517809274392190059938274315035097108977610565066656853492929507207804643381108991791052863

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

4, 1

bits:

0.4150374992788438185462610560521834912401855923075189395442473454589017722056414374777195250819117579

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1/4

nats:

1.030628859797199251687327863289275914151846870331852045806853222237119376195634123814160518459749872

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1/4

bits:

1.486883145026466109229811878652904679409604149277825599422491559888243458630220675267245106396013485

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1/3

nats:

0.7942906570332520080994882939430618017503150249708994172213356511924223664195819010853302779771792565

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1/3

bits:

1.145919191926309116065604616974906555026510050318805344985150104102128155918243775311765858691841496

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1/2

nats:

0.4133392865922339662817878711947632713324579039295799140116649440179973125633547973178974046989016116

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1/2

bits:

0.5963225389711979462790153413840845956794866870169296081613541379648395755689035067510695004148946074

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1

nats:

0.1335313926245226231463436209313499745894156734989045739026498785426010031570148790299314824013845356

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

8, 1

bits:

0.1926450779423958925580306827681691913589733740338592163227082759296791511378070135021390008297892149

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1/4

nats:

1.533241027345420370881897028071069078593345209064755803630545212936989643621779473491001061876408517

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1/4

bits:

2.211999226638737503759289614601560710413699355590095377214187228316565419745022977298605301619201582

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1/3

nats:

1.233391153577565063886503139832727164980479431828019342946031635627784848997877462119163226867251220

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1/3

bits:

1.779407300742670975438241598239781263031970325401831715374077662006557437404646844686912785656092292

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1/2

nats:

0.7254164411287308952536940793001730321399544470351321755383689159243442254459507810657151645358002128

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1/2

bits:

1.046554702195740735337970813281396657687677099641469163744745474821483497798508110813789890861270801

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1

nats:

0.06453852113757117167292391568399292812890862534975384283537781286190120695251213091970367507876305058

$q$-ary symmetric channel $\operatorname{QSC}(q,p)$

16, 1

bits:

0.09310940439148147067594162656279331537535419928293832748949094964296699559701622162757978172254160281

binary asymmetric channel $\operatorname{BAC}(p,q)$

1/4, 1/3

nats:

0.09026122059714477211807268942544290854872604219891196660428835896871353069900004070903129293730445667

binary asymmetric channel $\operatorname{BAC}(p,q)$

1/4, 1/3

bits:

0.1302194153400855231111773955181361864807968712452936795725745774187351048679367028688338113672736877

binary asymmetric channel $\operatorname{BAC}(p,q)$

1/4, 1/2

nats:

0.03384014101156195812827829358752877436139994506666547522760373598643686813598884140957838487414309109

binary asymmetric channel $\operatorname{BAC}(p,q)$

1/4, 1/2

bits:

0.04882100362036366670353322454634266882857357512882714294180072879352566226543719412779370042135021164

binary asymmetric channel $\operatorname{BAC}(p,q)$

1/3, 1/2

nats:

0.01436393555723356787905282270842431795698684005486328324799128528349645097492926115620570326399312257

binary asymmetric channel $\operatorname{BAC}(p,q)$

1/3, 1/2

bits:

0.02072277859606951759666955813934071864119740282323195070110658098009836216377204941657250707893789041

Definition

For a discrete memoryless channel with transition probabilities $W(y\mid x)$, the capacity [1] is $C=\max_{P_X} I(X;Y)$. This table gives $C$ for named finite-alphabet channels in the two logarithmic units nats and bits.

Parameters

channel

— channel family

shape

— shape parameter or tuple of shape parameters (for bsc and z the value is the probability $p$; for qsc it is $q,p$; for bac it is $p,q$)

unit

— logarithmic unit

Formulas

(1)

$C_{\mathrm{bits}}=C_{\mathrm{nats}}/\log 2$.

(2)

For the binary symmetric channel, $C_{\mathrm{bits}}(\operatorname{BSC}(p))=1-H_2(p)$, where $H_2(p)$ is the Bernoulli entropy in bits [3].

(3)

For the Z-channel, $C_{\mathrm{bits}}(Z(p))=\log_2(1+(1-p)p^{p/(1-p)})$ for $0<p<1$.

(4)

For the $q$-ary symmetric channel, $C_{\mathrm{bits}}(\operatorname{QSC}(q,p))=\log_2 q +(1-p)\log_2(1-p)+p\log_2(p/(q-1))$.

(5)

For $\operatorname{BAC}(p,q)$, let $h(t)=-t\log_2 t-(1-t)\log_2(1-t)$, $\delta=1-p-q$, $a=(h(p)-h(q))/\delta$, and $r=(1+2^a)^{-1}$. If $\delta\ne0$, then $C_{\mathrm{bits}}=h(r)-\frac{r-q}{\delta}h(p) -\frac{1-p-r}{\delta}h(q)$. If $\delta=0$, then the two input rows are equal and the capacity is $0$.

(6)

The binary erasure channel with erasure probability $\epsilon$ has $C_{\mathrm{bits}}=1-\epsilon$ [4].

Comments

(7)

The binary symmetric channel flips a bit with probability $p$. The Z-channel sends $0$ to $0$ with probability $1$, sends $1$ to $0$ with probability $p$, and sends $1$ to $1$ with probability $1-p$ [5]. The $q$-ary symmetric channel preserves its input with probability $1-p$ and sends it to each other symbol with probability $p/(q-1)$.

(8)

The binary asymmetric channel has $\Pr(Y=1\mid X=0)=p$ and $\Pr(Y=0\mid X=1)=q$. Rows with $p=q$ are the binary symmetric channel, rows with $p=0$ or $q=0$ are Z-channels after relabelling, and the table stores the remaining cases with $p<q$.

(9)

The binary erasure channel has capacity $1-\epsilon$ bits. It is recorded by Formula (6), not as a fifth channel family. Noiseless and input-independent capacities are used as exact validation controls rather than repeated as table entries.

(10)

The nats rows use the natural logarithm, and the bits rows use the base-two logarithm.

(11)

Probabilities lie in $[0,1]$, and the alphabet size $q$ of the symmetric channel is an integer at least $2$. Terms $0\log 0$ are interpreted as $0$. The Z-channel has capacity $1$ bit at $p=0$ and $0$ at $p=1$. A $q$-ary symmetric channel has capacity $0$ at $p=(q-1)/q$; at $p=1$ its capacity is $\log_2(q/(q-1))$, which is not zero.

(12)

For $\operatorname{QSC}(3,1/3)$, each conditional output distribution is a permutation of $(2/3,1/6,1/6)$ and has entropy $\log_2 3-1/3$. Its capacity is therefore exactly $1/3$ bit or $(\log 2)/3$ nats.

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField

R = RealBallField(numberdb.bits(100, losing=128))
p = R(QQ(1) / QQ(4))
1 + p * p.log() / R(2).log() + (1 - p) * (1 - p).log() / R(2).log()

References

[1]

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, second edition, Wiley-Interscience, Hoboken, NJ, 2006. (doi)

Links

[2]

Wikipedia: Channel capacity

[3]

Wikipedia: Binary symmetric channel

[4]

Wikipedia: Binary erasure channel

[5]

Wikipedia: Z-channel

Similar tables

Shannon entropies of discrete probability distributions — the BSC capacity is $1$ minus the Bernoulli entropy in bits

Capacity of the $(d,k)$ run-length-limited constrained codes — stores capacities of constrained noiseless systems rather than noisy memoryless channels

Differential entropies of continuous probability distributions — uses the same nats and bits logarithmic units for continuous distributions

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds both logarithmic units for BSC probabilities $1/4,1/3$ and Z-channel probabilities $1/4,1/3,1/2,2/3,3/4$. Halves, thirds and quarters are a small selection of simple binary randomizations; the Z-channel keeps the complementary probabilities because its direction makes their capacities different. For each $q\in\{3,4,8,16\}$, it holds QSC probabilities $1/4,1/3,1/2,1$, adding the informative never-correct limit; $3$ is the smallest nonbinary alphabet and $4,8,16$ encode two, three and four bits per symbol. BAC pairs are $(1/4,1/3),(1/4,1/2),(1/3,1/2)$, unequal mixtures of the same simple binary randomizations. Noiseless and input-independent channels are controls only. These are selected reference points, not a decimal grid or an exhaustive range)

How they were obtained:

Approximate entries have 100 significant decimal digits, enclosed by Sage Arb real-ball evaluation of the closed forms with 128 guard bits. The exact $1/3$-bit QSC entry is proved independently from row permutations, equal column sums and rational prime-log coefficients.

more

Zero capacities and noiseless integer bit capacities are identified algebraically for the controls, not inferred from rounded digits. Every written entry is independently checked from its exact rational transition matrix using MPFI interval arithmetic: achievable mutual information gives a lower bound and the maximum row divergence from the induced output law gives an upper bound. Binary input weights are selected by sign-certified rational bisection; the symmetric channels use a uniform input, accepted only when the two bounds agree to the required precision. Each approximate written interval contains the entire independent capacity enclosure; all MPFR endpoints are preserved by exact rational conversion. The matrix checker first passes noiseless, input-independent, binary-erasure and Z-channel controls. Run measurements and hashes accompany the generator.