682:
5758:
217:
22:
5178:
5163:
5753:{\displaystyle {\begin{aligned}\mathbb {E} _{E}\left\right]&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\mathbb {E} \\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}\mathbb {E} &&\sum _{y\in B_{0}}p(y|E(m))\leqslant 1\\&\leqslant 2^{-{\epsilon ^{2}}n}+2^{k+H(p+\epsilon )n-n}&&\mathbb {E} \leqslant 2^{k+H(p+\epsilon )n-n}{\text{ (see above)}}\\&\leqslant 2^{-\delta n}\end{aligned}}}
4689:
1407:
7734:, but it does not give us an idea of any explicit codes which achieve that rate. In fact such codes are typically constructed to correct only a small fraction of errors with a high probability, but achieve a very good rate. The first such code was due to George D. Forney in 1966. The code is a concatenated code by concatenating two different kinds of codes.
5158:{\displaystyle {\begin{aligned}\Pr _{e\in {\text{BSC}}_{p}}&=\sum _{y\in \{0,1\}^{n}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant \sum _{y\notin B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\end{aligned}}}
1081:
554:
9857:
used for memory storage: the channel input represents a bit being written to the disk and the output corresponds to the bit later being read. Error could arise from the magnetization flipping, background noise or the writing head making an error. Other objects which the binary symmetric channel can
7654:
Very recently, a lot of work has been done and is also being done to design explicit error-correcting codes to achieve the capacities of several standard communication channels. The motivation behind designing such codes is to relate the rate of the code with the fraction of errors which it can
8707:
3163:. We achieve this by eliminating half of the codewords from the code with the argument that the proof for the decoding error probability holds for at least half of the codewords. The latter method is called expurgation. This gives the total process the name
936:
1402:{\displaystyle {\begin{aligned}I(X;Y)&=H(Y)-H(Y|X)\\&=H(Y)-\sum _{x\in \{0,1\}}{p_{X}(x)H(Y|X=x)}\\&=H(Y)-\sum _{x\in \{0,1\}}{p_{X}(x)}\operatorname {H} _{\text{b}}(p)\\&=H(Y)-\operatorname {H} _{\text{b}}(p),\end{aligned}}}
1527:. The entropy of a binary variable is at most 1 bit, and equality is attained if its probability distribution is uniform. It therefore suffices to exhibit an input distribution that yields a uniform probability distribution for the output
330:
6116:
5939:
3831:
8543:
9217:
6319:
770:
9315:
4227:
1668:
2401:
3690:
4500:
From the above analysis, we calculate the probability of the event that the decoded codeword plus the channel noise is not the same as the original message sent. We shall introduce some symbols here. Let
8976:
1547:. For this, note that it is a property of any binary symmetric channel that a uniform probability distribution of the input results in a uniform probability distribution of the output. Hence the value
1070:
2109:
7796:
7644:
4020:
5183:
4694:
1987:
1086:
335:
7582:
175:
3947:
812:
7319:
The intuition behind the proof is however showing the number of errors to grow rapidly as the rate grows beyond the channel capacity. The idea is the sender generates messages of dimension
8216:
3399:
202:
7183:
2787:
2598:
2249:
2179:
8893:
7705:
have been to correct a lesser number of errors with a high probability, and to achieve the highest possible rate. Shannon's theorem gives us the best rate which could be achieved over a
4312:
9034:
9092:
9605:
8399:, a Reed-Solomon code would have been the first code to have come in mind. However, we would see that the construction of such a code cannot be done in polynomial time. This is why a
7909:
6678:
4683:
9728:
9538:
4366:
3611:
9448:
1940:
1892:
8301:
6472:
4141:
7440:
6882:
6716:
2697:
4420:
8098:
9477:
8736:
8535:
8366:
8330:
7825:
7732:
7366:
3263:
3117:
3068:
2877:
2832:
2643:
2496:
2294:
1767:
1715:
6618:
4459:
2924:
824:
597:
9839:
9632:
9372:
9246:
8428:
8397:
8042:
8015:
7856:
7313:
3529:
9812:
9504:
9419:
9345:
8458:
8270:
8243:
8128:
6643:
7703:
7678:
7103:
6987:
7984:
7141:
7084:
7025:
6968:
2447:
671:
7943:
7227:
4545:
3874:
3218:
3023:
2047:
9655:
9565:
1610:
1525:
1457:
989:
631:
8062:
6901:
6833:
6579:
6554:
6529:
6433:
5781:
6765:
4055:
9785:
9755:
9686:
9127:
8810:
8763:
7514:
7487:
7287:
7246:
6814:
6396:
6173:
6146:
4621:
2983:
7395:
4594:
3558:
3451:
1574:
1489:
1857:
7268:
1688:
gives a result about the rate of information that can be transmitted through a communication channel with arbitrarily low error. We study the particular case of
9392:
8783:
8506:
8486:
8168:
8148:
7876:
7460:
7337:
7045:
6929:
6795:
6496:
6366:
6342:
5962:
4565:
4479:
4095:
4075:
3854:
3494:
3471:
3422:
3291:
3198:
3161:
3141:
3088:
3003:
2944:
2717:
2516:
2467:
2027:
2007:
1831:
1811:
1791:
1738:
1545:
549:{\displaystyle {\begin{aligned}\operatorname {Pr} &=1-p\\\operatorname {Pr} &=p\\\operatorname {Pr} &=p\\\operatorname {Pr} &=1-p\end{aligned}}}
318:
294:
274:
250:
10042:
10038:
10034:
10030:
5970:
5793:
633:, then the receiver can swap the output (interpret 1 when it sees 0, and vice versa) and obtain an equivalent channel with crossover probability
8702:{\displaystyle R(C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1-H(p)-{\frac {\epsilon }{2}})\geq 1-H(p)-\epsilon }
3706:
2518:
or in effect the rate of the channel is bounded by the quantity stated in the theorem. The decoding error probability is exponentially small.
9136:
6181:
711:
9251:
4146:
1615:
2304:
8898:
996:
10000:
9881:
to a BSC. Conversely, being able to transmit effectively over the BSC can give rise to solutions for more complicated channels.
5944:
Now we can change the order of summation in the expectation with respect to the message and the choice of the encoding function
3616:
2052:
9983:
7748:
7587:
113:, and otherwise is received correctly. This model can be applied to varied communication channels such as telephone lines or
3952:
9841:
please read the following references. Recently a few other codes have also been constructed for achieving the capacities.
1945:
10065:
7519:
135:
778:
10020:
65:
43:
36:
8173:
3298:
180:
7146:
3882:
2722:
2533:
2184:
2114:
10029:
Atri Rudra's course on Error
Correcting Codes: Combinatorics, Algorithms, and Applications (Fall 2007), Lectures
8815:
4232:
8981:
681:
9890:
9039:
2947:
9570:
7881:
6648:
4626:
9691:
9509:
9424:
1907:
1862:
1685:
208:. Codes including Forney's code have been designed to transmit information efficiently across the channel.
121:
8279:
6438:
4100:
3692:. In other words, the errors due to noise take the transmitted codeword closer to another encoded message.
7400:
6837:
2648:
4371:
1459:) equals the binary entropy function, which leads to the third line and this can be further simplified.
931:{\displaystyle \operatorname {H} _{\text{b}}(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}
8067:
4321:
3566:
9453:
8712:
8511:
8335:
8306:
7801:
7708:
7342:
3223:
3093:
3028:
2837:
2792:
2603:
2472:
2254:
1743:
1691:
6584:
4425:
2885:
562:
9817:
9610:
9350:
9224:
8406:
8375:
8020:
7993:
7834:
7291:
6683:
4143:
is its volume. Using approximation to estimate the number of codewords in the
Hamming ball, we have
3499:
105:(a zero or a one), and the receiver will receive a bit. The bit will be "flipped" with a "crossover
9790:
9482:
9397:
9323:
8436:
8248:
8221:
8106:
30:
7686:
7661:
7088:
6972:
7948:
7107:
7050:
6991:
6934:
2413:
815:
689:-axis) that can be used for payload based on how noisy the channel is (probability of bit flips;
636:
321:
220:
The binary symmetric channel sees each bit of a message transmitted correctly with probability 1–
205:
10081:
9878:
7914:
7681:
7188:
6767:
is the best rate one can achieve over a binary symmetric channel. Formally the theorem states:
6399:
4504:
3859:
3203:
3008:
2032:
90:
47:
9637:
9547:
6623:
1579:
1494:
1419:
958:
602:
8047:
6886:
6818:
6501:
6405:
5766:
10010:
7646:, a case we would like to avoid to keep the decoding error probability exponentially small.
6735:
4025:
9874:
9763:
9733:
9664:
9105:
8788:
8741:
7492:
7465:
7272:
7231:
6799:
6374:
6151:
6124:
4599:
2956:
2527:
7371:
4570:
3534:
3427:
1550:
1465:
8:
10053:
10049:
1836:
1413:
7250:
6559:
6534:
1773:
consisting of n independent random bits (n is defined below) where each random bit is a
10048:
Madhu Sudan's course on
Algorithmic Introduction to Coding Theory (Fall 2001), Lecture
10006:
9377:
8768:
8491:
8471:
8400:
8153:
8133:
7861:
7516:
possible values. If there is any confusion between any two messages, it is likely that
7445:
7322:
7030:
6914:
6780:
6481:
6351:
6327:
5947:
4550:
4464:
4080:
4060:
3839:
3479:
3456:
3407:
3276:
3183:
3146:
3126:
3073:
2988:
2929:
2702:
2501:
2452:
2012:
1992:
1816:
1796:
1776:
1723:
1530:
952:
303:
279:
259:
235:
98:
2498:, there is a very high probability of recovering the original message by decoding, if
1412:
where the first and second step follows from the definition of mutual information and
10016:
9979:
7743:
6531:
messages from the sorted order. This essentially gives us another encoding function
2985:
satisfies the conclusion of theorem, by integration over the probabilities. Suppose
2880:
698:
129:
6111:{\displaystyle \mathbb {E} _{E}\left\neq m\right]\right]\leqslant 2^{-\delta n}.}
5934:{\displaystyle \mathbb {E} _{m}\left\neq m\right]\right]\leqslant 2^{-\delta n}.}
1770:
297:
2699:
is selected at random (with equal probabilities). For a given encoding function
216:
10059:
9541:
5169:
3697:
3266:
10075:
9859:
7658:
The approach behind the design of codes which meet the channel capacities of
6121:
Hence in conclusion, by probabilistic method, we have some encoding function
94:
9845:
codes have been considered for this purpose for their faster decoding time.
9688:. This when expressed in asymptotic terms, gives us an error probability of
1612:. We conclude that the channel capacity for our binary symmetric channel is
1416:
respectively. The entropy at the output for a given and fixed input symbol (
256:, is a channel with binary input and binary output and probability of error
9993:
9870:
9869:
This channel is often used by theorists because it is one of the simplest
3826:{\displaystyle Pr_{e\in {\text{BSC}}_{p}}\leqslant 2^{-{\epsilon ^{2}}n}.}
8465:
8461:
4315:
3270:
106:
10062:
C. E Shannon, ACM SIGMOBILE Mobile
Computing and Communications Review.
9854:
114:
9212:{\displaystyle y_{i}^{\prime }=D_{\text{in}}(y_{i}),\quad i\in (0,N)}
7368:
introduces transmission errors. When the capacity of the channel is
6314:{\displaystyle \mathbb {E} _{m}\left\right]\leqslant 2^{-\delta n}.}
765:{\displaystyle \ C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p),}
10002:
Error-Correcting Codes: Constructions and
Algorithms], Autumn 2006.
9310:{\displaystyle y^{\prime }=(y_{1}^{\prime }\ldots y_{N}^{\prime })}
128:, saying that information can be transmitted at any rate up to the
10068:
by Tom
Richardson and Rudiger Urbanke., Cambridge University Press
4222:{\displaystyle {\text{Vol}}(B(y,(p+\epsilon )n))\approx 2^{H(p)n}}
2410:
What this theorem actually implies is, a message when picked from
3273:
of the received codeword along with the noise does not give back
1663:{\displaystyle C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p)}
7798:
to achieve the capacity of the noisy-channel coding theorem for
6398:
messages by their decoding error probabilities. Now by applying
3560:. This condition is mainly used to make the calculations easier.
2396:{\displaystyle \Pr _{e\in {\text{BSC}}_{p}}\leq 2^{-{\delta }n}}
320:
the received variable, then the channel is characterized by the
955:
between input and output for all possible input distributions
8738:
capacity. We further note that the encoding and decoding of
6732:
The converse of the capacity theorem essentially states that
2953:
The proof continues by showing that at least one such choice
2600:
that is selected at random. This means that for each message
9757:
is exponentially small as the noisy-channel coding theorem.
8971:{\displaystyle Nt_{\text{in}}(k)+t_{\text{out}}(N)=N^{O(1)}}
6474:. Thus in order to confirm that the above bound to hold for
3424:
be the received codeword. In order for the decoded codeword
9842:
9658:
8273:
7987:
6908:
6904:
6402:, we can show the decoding error probability for the first
1065:{\displaystyle C=\max _{p_{X}(x)}\left\{\,I(X;Y)\,\right\}}
6344:. But we need to make sure that the above bound holds for
9930:
9863:
9858:
model include a telephone or radio communication line or
6727:
3700:
to ensure the non occurrence of the first event; we get:
3685:{\displaystyle \Delta (y,E(m'))\leqslant \Delta (y,E(m))}
2926:
is as small as possible (with ties broken arbitrarily). (
2111:, there exists a pair of encoding and decoding functions
2104:{\displaystyle k\leq \lfloor (1-H(p+\epsilon ))n\rfloor }
702:
102:
3879:
For the second event, we note that the probability that
8895:. Further, the decoding algorithm described takes time
7791:{\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}
7639:{\displaystyle k\geq \lceil (1-H(p+\epsilon )n)\rceil }
10012:
Information Theory, Inference, and
Learning Algorithms
9920:
9918:
9514:
9429:
6659:
4015:{\displaystyle {\text{Vol}}(B(y,(p+\epsilon )n)/2^{n}}
3143:. Next we extend this result to work for all messages
1962:
1918:
685:
Graph showing the proportion of a channel’s capacity (
232:
A binary symmetric channel with crossover probability
9820:
9793:
9766:
9736:
9694:
9667:
9640:
9613:
9573:
9550:
9512:
9485:
9456:
9427:
9400:
9380:
9353:
9326:
9254:
9227:
9139:
9108:
9042:
8984:
8901:
8818:
8791:
8771:
8744:
8715:
8546:
8514:
8494:
8474:
8439:
8409:
8378:
8338:
8309:
8282:
8251:
8224:
8176:
8156:
8136:
8109:
8070:
8050:
8023:
7996:
7951:
7917:
7884:
7864:
7837:
7804:
7751:
7711:
7689:
7664:
7590:
7522:
7495:
7468:
7448:
7403:
7374:
7345:
7325:
7294:
7275:
7253:
7234:
7191:
7149:
7110:
7091:
7053:
7033:
6994:
6975:
6937:
6917:
6889:
6840:
6821:
6802:
6783:
6738:
6686:
6651:
6626:
6587:
6562:
6537:
6504:
6484:
6441:
6408:
6377:
6354:
6330:
6184:
6154:
6127:
5973:
5950:
5796:
5769:
5181:
5172:
above. Now taking expectation on both sides we have,
5168:
We get the last inequality by our analysis using the
4692:
4629:
4602:
4573:
4553:
4507:
4467:
4428:
4374:
4324:
4235:
4149:
4103:
4083:
4063:
4028:
3955:
3885:
3862:
3842:
3709:
3619:
3569:
3537:
3502:
3482:
3459:
3430:
3410:
3301:
3279:
3226:
3206:
3186:
3149:
3129:
3123:. At this point, the proof works for a fixed message
3096:
3076:
3031:
3011:
2991:
2959:
2932:
2888:
2840:
2795:
2789:
is specified as follows: given any received codeword
2725:
2705:
2651:
2606:
2536:
2504:
2475:
2455:
2416:
2307:
2257:
2187:
2117:
2055:
2035:
2015:
1995:
1948:
1910:
1865:
1839:
1819:
1799:
1779:
1746:
1726:
1694:
1618:
1582:
1553:
1533:
1497:
1468:
1422:
1084:
999:
961:
827:
781:
714:
639:
605:
565:
333:
306:
282:
262:
238:
183:
138:
9951:
1576:
will be 1 when we choose a uniform distribution for
132:
with arbitrarily low error. The channel capacity is
9915:
9479:are independent, the expected number of errors for
6324:At this point, the proof works for a fixed message
1982:{\displaystyle 0<\epsilon <{\tfrac {1}{2}}-p}
9903:
9833:
9806:
9779:
9749:
9730:. Thus the achieved decoding error probability of
9722:
9680:
9649:
9626:
9599:
9559:
9532:
9498:
9471:
9442:
9413:
9386:
9374:. Now since the probability of error at any index
9366:
9339:
9309:
9240:
9211:
9121:
9086:
9028:
8970:
8887:
8804:
8777:
8757:
8730:
8701:
8529:
8500:
8480:
8452:
8422:
8391:
8360:
8324:
8295:
8264:
8237:
8210:
8162:
8142:
8122:
8092:
8056:
8036:
8009:
7978:
7937:
7903:
7870:
7850:
7819:
7790:
7726:
7697:
7672:
7638:
7577:{\displaystyle 2^{k}2^{H(p+\epsilon )n}\geq 2^{n}}
7576:
7508:
7489:. The output of the channel on the other hand has
7481:
7454:
7434:
7389:
7360:
7331:
7307:
7281:
7262:
7240:
7221:
7177:
7135:
7097:
7078:
7039:
7019:
6981:
6962:
6923:
6895:
6876:
6827:
6808:
6789:
6759:
6710:
6672:
6637:
6612:
6573:
6548:
6523:
6490:
6466:
6427:
6390:
6360:
6336:
6313:
6167:
6140:
6110:
5956:
5933:
5775:
5752:
5157:
4677:
4615:
4588:
4559:
4539:
4473:
4453:
4414:
4360:
4306:
4221:
4135:
4089:
4069:
4049:
4014:
3941:
3868:
3848:
3825:
3684:
3605:
3552:
3523:
3488:
3465:
3445:
3416:
3393:
3293:on decoding. That is to say, we need to estimate:
3285:
3257:
3212:
3192:
3155:
3135:
3111:
3082:
3062:
3017:
2997:
2977:
2938:
2918:
2871:
2826:
2781:
2711:
2691:
2637:
2592:
2510:
2490:
2461:
2441:
2395:
2288:
2243:
2173:
2103:
2041:
2021:
2001:
1981:
1934:
1886:
1851:
1825:
1805:
1785:
1761:
1732:
1709:
1662:
1604:
1568:
1539:
1519:
1483:
1451:
1401:
1064:
983:
930:
806:
764:
665:
625:
591:
548:
312:
288:
268:
244:
196:
170:{\displaystyle 1-\operatorname {H} _{\text{b}}(p)}
169:
3090:chosen randomly, the probability of failure over
10073:
7151:
6718:. This expurgation process completes the proof.
6203:
6009:
5832:
5204:
4698:
3320:
2309:
1007:
807:{\displaystyle \operatorname {H} _{\text{b}}(p)}
101:. In this model, a transmitter wishes to send a
9760:We have given a general technique to construct
9544:, we have bound error probability of more than
8765:can be done in polynomial time with respect to
3496:does not lie within the Hamming ball of radius
1679:
4318:, we can upper bound the existence of such an
1075:The mutual information can be reformulated as
228:, due to noise across the transmission medium.
9097:
8218:. Additionally, we have a decoding algorithm
8211:{\displaystyle 1-H(p)-{\frac {\epsilon }{2}}}
6581:with a decoding error probability of at most
4547:denote the probability of receiving codeword
3394:{\displaystyle \mathbb {E} _{E}\left\right].}
197:{\displaystyle \operatorname {H} _{\text{b}}}
7633:
7597:
7178:{\displaystyle \Pr _{e\in {\text{BSC}}_{p}}}
7124:
7111:
7067:
7054:
7008:
6995:
6951:
6938:
6890:
6822:
4792:
4779:
4349:
4336:
3942:{\displaystyle E(m')\in B(y,(p+\epsilon )n)}
3594:
3581:
3246:
3233:
3051:
3038:
2860:
2847:
2815:
2802:
2782:{\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}
2770:
2757:
2745:
2732:
2680:
2667:
2626:
2613:
2593:{\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}
2581:
2568:
2556:
2543:
2430:
2417:
2277:
2264:
2244:{\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}
2232:
2219:
2207:
2194:
2174:{\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}
2162:
2149:
2137:
2124:
2098:
2062:
1297:
1285:
1197:
1185:
9973:
9936:
8888:{\displaystyle O(N^{2})+O(Nk^{2})=O(N^{2})}
6680:we bound the decoding error probability to
4307:{\displaystyle 2^{H(p)n}/2^{n}=2^{H(p)n-n}}
3025:are fixed. First we show that, for a fixed
9540:by linearity of expectation. Now applying
9029:{\displaystyle t_{\text{out}}(N)=N^{O(1)}}
8064:fraction of worst case errors and runs in
3473:, one of the following events must occur:
2526:The theorem can be proved directly with a
2449:, encoded with a random encoding function
9974:Cover, Thomas M.; Thomas, Joy A. (1991).
9853:The binary symmetric channel can model a
9087:{\displaystyle t_{\text{in}}(k)=2^{O(k)}}
6187:
5993:
5976:
5816:
5799:
5637:
5457:
5360:
5188:
4229:. Hence the above probability amounts to
3304:
1056:
1037:
66:Learn how and when to remove this message
9862:, from which the daughter cells contain
9600:{\displaystyle e^{\frac {-\gamma N}{6}}}
7904:{\displaystyle 1-{\frac {\epsilon }{2}}}
680:
215:
29:This article includes a list of general
8537:, by the noisy-channel coding theorem.
6673:{\displaystyle \delta -{\tfrac {1}{n}}}
6556:with a corresponding decoding function
5763:by appropriately choosing the value of
4678:{\displaystyle B(E(m),(p+\epsilon )n).}
2251:respectively, such that every message
951:The capacity is defined as the maximum
10074:
10060:A mathematical theory of communication
10005:
9957:
9924:
9909:
9873:channels to analyze. Many problems in
9723:{\displaystyle 2^{-\Omega (\gamma N)}}
9533:{\displaystyle {\tfrac {\gamma N}{2}}}
6728:Converse of Shannon's capacity theorem
6148:and a corresponding decoding function
3836:This is exponentially small for large
1462:In the last line, only the first term
9443:{\displaystyle {\tfrac {\gamma }{2}}}
6903:then the following is true for every
1935:{\displaystyle p<{\tfrac {1}{2}},}
1887:{\displaystyle e\in {\text{BSC}}_{p}}
9866:information from their parent cell.
9787:. For more detailed descriptions on
8296:{\displaystyle {\frac {\gamma }{2}}}
7462:. The maximum number of messages is
7397:, the number of errors is typically
6467:{\displaystyle 2\cdot 2^{-\delta n}}
4136:{\displaystyle {\text{Vol}}(B(x,r))}
701:of the binary symmetric channel, in
15:
8508:, whose rate meets the capacity of
8464:by exhaustively searching from the
7435:{\displaystyle 2^{H(p+\epsilon )n}}
6877:{\displaystyle (1-H(p+\epsilon )n)}
2692:{\displaystyle E(m)\in \{0,1\}^{n}}
13:
9703:
9299:
9281:
9260:
9150:
6498:, we could just trim off the last
5783:. Since the above bound holds for
4437:
4415:{\displaystyle \leq 2^{k+H(p)n-n}}
3741:
3655:
3620:
2889:
1639:
1491:depends on the input distribution
1371:
1324:
829:
783:
738:
185:
146:
35:it lacks sufficient corresponding
14:
10093:
9996:. MIT Press, Cambridge, MA, 1966.
9320:Note that each block of code for
9102:A natural decoding algorithm for
8785:. As a matter of fact, encoding
8093:{\displaystyle t_{\text{out}}(N)}
4495:Continuation of proof (detailed)
4361:{\displaystyle m'\in \{0,1\}^{k}}
3606:{\displaystyle m'\in \{0,1\}^{k}}
224:and incorrectly with probability
9472:{\displaystyle {\text{BSC}}_{p}}
8731:{\displaystyle {\text{BSC}}_{p}}
8530:{\displaystyle {\text{BSC}}_{p}}
8361:{\displaystyle t_{\text{in}}(N)}
8325:{\displaystyle {\text{BSC}}_{p}}
7820:{\displaystyle {\text{BSC}}_{p}}
7737:
7727:{\displaystyle {\text{BSC}}_{p}}
7361:{\displaystyle {\text{BSC}}_{p}}
3258:{\displaystyle m\in \{0,1\}^{k}}
3119:noise is exponentially small in
3112:{\displaystyle {\text{BSC}}_{p}}
3063:{\displaystyle m\in \{0,1\}^{k}}
2872:{\displaystyle m\in \{0,1\}^{k}}
2827:{\displaystyle y\in \{0,1\}^{n}}
2638:{\displaystyle m\in \{0,1\}^{k}}
2530:. Consider an encoding function
2491:{\displaystyle {\text{BSC}}_{p}}
2289:{\displaystyle m\in \{0,1\}^{k}}
1762:{\displaystyle {\text{BSC}}_{p}}
1710:{\displaystyle {\text{BSC}}_{p}}
20:
9848:
9187:
6613:{\displaystyle 2^{-\delta n+1}}
4454:{\displaystyle 2^{-\Omega (n)}}
3453:not to be equal to the message
3175:Continuation of proof (sketch)
2919:{\displaystyle \Delta (y,E(m))}
1859:. We indicate this by writing "
592:{\displaystyle 0\leq p\leq 1/2}
10015:. Cambridge University Press.
9978:. Hoboken, New Jersey: Wiley.
9976:Elements of Information Theory
9942:
9834:{\displaystyle C_{\text{out}}}
9715:
9706:
9627:{\displaystyle C_{\text{out}}}
9367:{\displaystyle C_{\text{out}}}
9304:
9268:
9241:{\displaystyle D_{\text{out}}}
9206:
9194:
9181:
9168:
9079:
9073:
9059:
9053:
9021:
9015:
9001:
8995:
8963:
8957:
8943:
8937:
8921:
8915:
8882:
8869:
8860:
8844:
8835:
8822:
8690:
8684:
8669:
8653:
8647:
8635:
8632:
8613:
8607:
8594:
8585:
8572:
8563:
8550:
8423:{\displaystyle C_{\text{out}}}
8392:{\displaystyle C_{\text{out}}}
8355:
8349:
8192:
8186:
8087:
8081:
8037:{\displaystyle C_{\text{out}}}
8010:{\displaystyle D_{\text{out}}}
7973:
7961:
7851:{\displaystyle C_{\text{out}}}
7630:
7624:
7612:
7600:
7553:
7541:
7424:
7412:
7384:
7378:
7308:{\displaystyle {\frac {1}{2}}}
7257:
7216:
7207:
7201:
7195:
7092:
6976:
6871:
6865:
6853:
6841:
6754:
6748:
6711:{\displaystyle 2^{-\delta 'n}}
6270:
6261:
6255:
6242:
6062:
6053:
6047:
6041:
5885:
5876:
5870:
5864:
5701:
5689:
5669:
5658:
5652:
5641:
5619:
5607:
5546:
5543:
5537:
5530:
5523:
5489:
5478:
5472:
5461:
5392:
5381:
5375:
5364:
5356:
5353:
5347:
5340:
5333:
5264:
5255:
5246:
5240:
5234:
5228:
5140:
5134:
5120:
5117:
5111:
5104:
5097:
5022:
5016:
5002:
4999:
4993:
4986:
4979:
4939:
4933:
4919:
4916:
4910:
4903:
4896:
4849:
4843:
4829:
4826:
4820:
4813:
4806:
4758:
4749:
4740:
4734:
4728:
4722:
4669:
4663:
4651:
4645:
4639:
4633:
4583:
4577:
4534:
4531:
4525:
4518:
4511:
4461:, as desired by the choice of
4446:
4440:
4398:
4392:
4290:
4284:
4250:
4244:
4211:
4205:
4191:
4188:
4182:
4170:
4161:
4155:
4130:
4127:
4115:
4109:
4057:is the Hamming ball of radius
4044:
4032:
3994:
3988:
3976:
3967:
3961:
3936:
3930:
3918:
3909:
3900:
3889:
3789:
3783:
3771:
3765:
3762:
3756:
3744:
3738:
3679:
3676:
3670:
3658:
3649:
3646:
3635:
3623:
3547:
3541:
3524:{\displaystyle (p+\epsilon )n}
3515:
3503:
3440:
3434:
3380:
3371:
3362:
3356:
3350:
3344:
3165:random coding with expurgation
2972:
2960:
2913:
2910:
2904:
2892:
2754:
2661:
2655:
2565:
2369:
2360:
2351:
2345:
2339:
2333:
2216:
2146:
2092:
2089:
2077:
2065:
1657:
1651:
1599:
1593:
1563:
1557:
1514:
1508:
1478:
1472:
1446:
1433:
1426:
1389:
1383:
1364:
1358:
1342:
1336:
1319:
1313:
1268:
1262:
1245:
1232:
1225:
1219:
1213:
1168:
1162:
1146:
1139:
1132:
1123:
1117:
1104:
1092:
1053:
1041:
1027:
1021:
978:
972:
894:
882:
847:
841:
801:
795:
756:
750:
523:
510:
497:
474:
461:
448:
425:
412:
399:
370:
357:
344:
164:
158:
1:
9999:Venkat Guruswamy's course on
9967:
9807:{\displaystyle C_{\text{in}}}
9499:{\displaystyle D_{\text{in}}}
9414:{\displaystyle D_{\text{in}}}
9340:{\displaystyle C_{\text{in}}}
8453:{\displaystyle C_{\text{in}}}
8276:error probability of at most
8265:{\displaystyle C_{\text{in}}}
8238:{\displaystyle D_{\text{in}}}
8123:{\displaystyle C_{\text{in}}}
2296:has the following property:
211:
7698:{\displaystyle {\text{BEC}}}
7673:{\displaystyle {\text{BSC}}}
7098:{\displaystyle \rightarrow }
6982:{\displaystyle \rightarrow }
6371:. For that, let us sort the
4491:
3171:
1686:noisy-channel coding theorem
1680:Noisy-channel coding theorem
942:
122:noisy-channel coding theorem
7:
9884:
9347:is considered a symbol for
7979:{\displaystyle k=O(\log N)}
7442:for a code of block length
7136:{\displaystyle \{0,1\}^{k}}
7079:{\displaystyle \{0,1\}^{n}}
7020:{\displaystyle \{0,1\}^{n}}
6963:{\displaystyle \{0,1\}^{k}}
6620:with the same rate. Taking
2948:maximum likelihood decoding
2442:{\displaystyle \{0,1\}^{k}}
676:
666:{\displaystyle 1-p\leq 1/2}
10:
10098:
9098:Decoding error probability
8130:is a code of block length
7986:. Additionally, we have a
7858:is a code of block length
3265:, we need to estimate the
2469:, and sent across a noisy
9937:Cover & Thomas (1991)
7938:{\displaystyle F_{2^{k}}}
7222:{\displaystyle D(E(m)+e)}
4540:{\displaystyle p(y|E(m))}
3869:{\displaystyle \epsilon }
3563:There is another message
3213:{\displaystyle \epsilon }
3018:{\displaystyle \epsilon }
2042:{\displaystyle \epsilon }
1989:, all sufficiently large
322:conditional probabilities
9896:
9650:{\displaystyle \gamma N}
9560:{\displaystyle \gamma N}
8044:which can correct up to
7649:
6638:{\displaystyle \delta '}
3220:. Given a fixed message
2719:, the decoding function
2521:
1605:{\displaystyle p_{X}(x)}
1520:{\displaystyle p_{X}(x)}
1452:{\displaystyle H(Y|X=x)}
984:{\displaystyle p_{X}(x)}
626:{\displaystyle p>1/2}
80:binary symmetric channel
9607:. Since the outer code
9567:errors occurring to be
8709:which almost meets the
8057:{\displaystyle \gamma }
6896:{\displaystyle \rceil }
6828:{\displaystyle \lceil }
6524:{\displaystyle 2^{k-1}}
6435:messages to be at most
6428:{\displaystyle 2^{k-1}}
5776:{\displaystyle \delta }
816:binary entropy function
206:binary entropy function
50:more precise citations.
9948:Richardson and Urbanke
9835:
9808:
9781:
9751:
9724:
9682:
9651:
9628:
9601:
9561:
9534:
9500:
9473:
9444:
9415:
9388:
9368:
9341:
9311:
9242:
9213:
9123:
9088:
9030:
8972:
8889:
8806:
8779:
8759:
8732:
8703:
8531:
8502:
8482:
8454:
8424:
8393:
8362:
8326:
8297:
8266:
8239:
8212:
8164:
8144:
8124:
8094:
8058:
8038:
8011:
7980:
7939:
7905:
7872:
7852:
7821:
7792:
7728:
7699:
7682:binary erasure channel
7674:
7640:
7584:. Hence we would have
7578:
7510:
7483:
7456:
7436:
7391:
7362:
7333:
7309:
7283:
7264:
7242:
7223:
7179:
7137:
7099:
7080:
7041:
7021:
6983:
6964:
6925:
6897:
6878:
6829:
6810:
6791:
6761:
6760:{\displaystyle 1-H(p)}
6712:
6674:
6639:
6614:
6575:
6550:
6525:
6492:
6468:
6429:
6392:
6362:
6338:
6315:
6169:
6142:
6112:
5958:
5935:
5777:
5754:
5159:
4679:
4617:
4590:
4561:
4541:
4475:
4455:
4416:
4362:
4308:
4223:
4137:
4091:
4071:
4051:
4050:{\displaystyle B(x,r)}
4016:
3943:
3870:
3850:
3827:
3686:
3607:
3554:
3525:
3490:
3467:
3447:
3418:
3395:
3287:
3259:
3214:
3194:
3157:
3137:
3113:
3084:
3064:
3019:
2999:
2979:
2940:
2920:
2873:
2834:, we find the message
2828:
2783:
2713:
2693:
2639:
2594:
2512:
2492:
2463:
2443:
2397:
2290:
2245:
2175:
2105:
2043:
2023:
2003:
1983:
1936:
1888:
1853:
1827:
1807:
1787:
1763:
1734:
1711:
1664:
1606:
1570:
1541:
1521:
1485:
1453:
1403:
1066:
985:
932:
808:
766:
694:
667:
627:
593:
550:
314:
290:
270:
246:
229:
198:
171:
91:communications channel
9836:
9809:
9782:
9780:{\displaystyle C^{*}}
9752:
9750:{\displaystyle C^{*}}
9725:
9683:
9681:{\displaystyle C^{*}}
9661:error probability of
9652:
9629:
9602:
9562:
9535:
9501:
9474:
9445:
9416:
9389:
9369:
9342:
9312:
9243:
9214:
9124:
9122:{\displaystyle C^{*}}
9089:
9031:
8973:
8890:
8807:
8805:{\displaystyle C^{*}}
8780:
8760:
8758:{\displaystyle C^{*}}
8733:
8704:
8532:
8503:
8483:
8455:
8425:
8394:
8363:
8327:
8298:
8267:
8240:
8213:
8165:
8145:
8125:
8095:
8059:
8039:
8012:
7981:
7940:
7906:
7873:
7853:
7822:
7793:
7742:Forney constructed a
7729:
7700:
7675:
7641:
7579:
7511:
7509:{\displaystyle 2^{n}}
7484:
7482:{\displaystyle 2^{k}}
7457:
7437:
7392:
7363:
7334:
7310:
7284:
7282:{\displaystyle \geq }
7265:
7243:
7241:{\displaystyle \neq }
7224:
7180:
7138:
7100:
7081:
7042:
7022:
6984:
6965:
6926:
6898:
6879:
6830:
6811:
6809:{\displaystyle \geq }
6792:
6762:
6713:
6675:
6640:
6615:
6576:
6551:
6526:
6493:
6469:
6430:
6393:
6391:{\displaystyle 2^{k}}
6363:
6339:
6316:
6170:
6168:{\displaystyle D^{*}}
6143:
6141:{\displaystyle E^{*}}
6113:
5959:
5936:
5778:
5755:
5160:
4680:
4618:
4616:{\displaystyle B_{0}}
4591:
4562:
4542:
4476:
4456:
4417:
4363:
4309:
4224:
4138:
4092:
4072:
4052:
4017:
3944:
3871:
3851:
3828:
3687:
3608:
3555:
3526:
3491:
3468:
3448:
3419:
3396:
3288:
3260:
3215:
3195:
3158:
3138:
3114:
3085:
3065:
3020:
3000:
2980:
2978:{\displaystyle (E,D)}
2941:
2921:
2874:
2829:
2784:
2714:
2694:
2640:
2595:
2513:
2493:
2464:
2444:
2398:
2291:
2246:
2176:
2106:
2044:
2024:
2004:
1984:
1937:
1889:
1854:
1828:
1808:
1788:
1764:
1735:
1712:
1665:
1607:
1571:
1542:
1522:
1486:
1454:
1404:
1067:
986:
933:
809:
767:
684:
668:
628:
594:
551:
315:
291:
271:
247:
219:
199:
172:
10066:Modern Coding Theory
9875:communication theory
9818:
9791:
9764:
9734:
9692:
9665:
9657:errors, this is the
9638:
9634:can correct at most
9611:
9571:
9548:
9510:
9483:
9454:
9425:
9398:
9378:
9351:
9324:
9252:
9225:
9137:
9106:
9040:
8982:
8899:
8816:
8789:
8769:
8742:
8713:
8544:
8512:
8492:
8472:
8437:
8407:
8376:
8336:
8307:
8280:
8249:
8222:
8174:
8154:
8134:
8107:
8068:
8048:
8021:
7994:
7949:
7915:
7882:
7862:
7835:
7802:
7749:
7709:
7687:
7662:
7588:
7520:
7493:
7466:
7446:
7401:
7390:{\displaystyle H(p)}
7372:
7343:
7339:, while the channel
7323:
7292:
7273:
7251:
7232:
7189:
7147:
7108:
7089:
7051:
7031:
6992:
6973:
6935:
6915:
6887:
6838:
6819:
6800:
6781:
6736:
6684:
6649:
6624:
6585:
6560:
6535:
6502:
6482:
6439:
6406:
6375:
6352:
6328:
6182:
6152:
6125:
5971:
5948:
5794:
5767:
5179:
4690:
4627:
4600:
4589:{\displaystyle E(m)}
4571:
4567:given that codeword
4551:
4505:
4465:
4426:
4372:
4322:
4233:
4147:
4101:
4081:
4061:
4026:
3953:
3883:
3860:
3840:
3707:
3617:
3567:
3553:{\displaystyle E(m)}
3535:
3500:
3480:
3457:
3446:{\displaystyle D(y)}
3428:
3408:
3299:
3277:
3224:
3204:
3184:
3147:
3127:
3094:
3074:
3029:
3009:
2989:
2957:
2930:
2886:
2838:
2793:
2723:
2703:
2649:
2604:
2534:
2528:probabilistic method
2502:
2473:
2453:
2414:
2305:
2255:
2185:
2115:
2053:
2033:
2013:
1993:
1946:
1908:
1863:
1837:
1817:
1797:
1777:
1744:
1724:
1692:
1616:
1580:
1569:{\displaystyle H(Y)}
1551:
1531:
1495:
1484:{\displaystyle H(Y)}
1466:
1420:
1082:
997:
959:
825:
779:
712:
637:
603:
563:
331:
304:
280:
260:
236:
181:
136:
9303:
9285:
9154:
8433:For the inner code
8372:For the outer code
6775: —
6400:Markov's inequality
4077:centered at vector
1902: —
1852:{\displaystyle 1-p}
1740:that characterizes
1414:conditional entropy
559:It is assumed that
296:is the transmitted
10007:MacKay, David J.C.
9994:Concatenated Codes
9831:
9804:
9777:
9747:
9720:
9678:
9647:
9624:
9597:
9557:
9530:
9528:
9496:
9469:
9450:and the errors in
9440:
9438:
9411:
9384:
9364:
9337:
9307:
9289:
9271:
9238:
9209:
9140:
9119:
9084:
9026:
8968:
8885:
8802:
8775:
8755:
8728:
8699:
8527:
8498:
8478:
8450:
8420:
8401:binary linear code
8389:
8358:
8322:
8293:
8262:
8235:
8208:
8160:
8140:
8120:
8090:
8054:
8034:
8007:
7976:
7935:
7901:
7868:
7848:
7817:
7788:
7724:
7695:
7670:
7636:
7574:
7506:
7479:
7452:
7432:
7387:
7358:
7329:
7305:
7279:
7263:{\displaystyle m]}
7260:
7238:
7219:
7175:
7174:
7133:
7095:
7076:
7037:
7017:
6979:
6960:
6921:
6893:
6874:
6825:
6806:
6787:
6773:
6757:
6708:
6670:
6668:
6635:
6610:
6574:{\displaystyle D'}
6571:
6549:{\displaystyle E'}
6546:
6521:
6488:
6464:
6425:
6388:
6358:
6334:
6311:
6226:
6165:
6138:
6108:
6032:
5954:
5931:
5855:
5773:
5750:
5748:
5519:
5455:
5329:
5227:
5155:
5153:
5093:
4975:
4892:
4802:
4721:
4675:
4613:
4586:
4557:
4537:
4471:
4451:
4412:
4358:
4304:
4219:
4133:
4087:
4067:
4047:
4012:
3939:
3866:
3846:
3823:
3682:
3603:
3550:
3521:
3486:
3463:
3443:
3414:
3391:
3343:
3283:
3255:
3210:
3190:
3153:
3133:
3109:
3080:
3060:
3015:
2995:
2975:
2936:
2916:
2869:
2824:
2779:
2709:
2689:
2635:
2590:
2508:
2488:
2459:
2439:
2393:
2332:
2286:
2241:
2171:
2101:
2039:
2019:
1999:
1979:
1971:
1932:
1927:
1900:
1884:
1849:
1823:
1803:
1783:
1759:
1730:
1707:
1660:
1602:
1566:
1537:
1517:
1481:
1449:
1399:
1397:
1301:
1201:
1062:
1031:
981:
953:mutual information
928:
804:
762:
695:
663:
623:
589:
546:
544:
310:
286:
266:
242:
230:
194:
167:
99:information theory
9992:G. David Forney.
9985:978-0-471-24195-9
9828:
9801:
9621:
9594:
9527:
9493:
9461:
9437:
9408:
9387:{\displaystyle i}
9361:
9334:
9235:
9165:
9050:
8992:
8934:
8912:
8778:{\displaystyle N}
8720:
8667:
8630:
8604:
8582:
8519:
8501:{\displaystyle k}
8481:{\displaystyle n}
8447:
8417:
8386:
8346:
8314:
8291:
8259:
8232:
8206:
8163:{\displaystyle k}
8143:{\displaystyle n}
8117:
8078:
8031:
8004:
7899:
7871:{\displaystyle N}
7845:
7809:
7785:
7772:
7744:concatenated code
7716:
7693:
7668:
7455:{\displaystyle n}
7350:
7332:{\displaystyle k}
7303:
7165:
7150:
7040:{\displaystyle D}
6924:{\displaystyle E}
6790:{\displaystyle k}
6771:
6723:
6722:
6667:
6491:{\displaystyle m}
6361:{\displaystyle m}
6337:{\displaystyle m}
6217:
6202:
6023:
6008:
5957:{\displaystyle E}
5846:
5831:
5787:message, we have
5718:
5717: (see above)
5497:
5433:
5307:
5218:
5203:
5071:
4953:
4870:
4768:
4712:
4697:
4560:{\displaystyle y}
4486:
4485:
4474:{\displaystyle k}
4153:
4107:
4090:{\displaystyle x}
4070:{\displaystyle r}
3959:
3849:{\displaystyle n}
3728:
3696:We can apply the
3489:{\displaystyle y}
3466:{\displaystyle m}
3417:{\displaystyle y}
3334:
3319:
3286:{\displaystyle m}
3193:{\displaystyle p}
3156:{\displaystyle m}
3136:{\displaystyle m}
3101:
3083:{\displaystyle E}
2998:{\displaystyle p}
2939:{\displaystyle D}
2712:{\displaystyle E}
2511:{\displaystyle k}
2480:
2462:{\displaystyle E}
2323:
2308:
2022:{\displaystyle p}
2002:{\displaystyle n}
1970:
1926:
1898:
1876:
1833:with probability
1826:{\displaystyle 0}
1806:{\displaystyle p}
1793:with probability
1786:{\displaystyle 1}
1751:
1733:{\displaystyle e}
1699:
1675:
1674:
1645:
1626:
1540:{\displaystyle Y}
1377:
1330:
1274:
1174:
1006:
926:
877:
835:
789:
744:
725:
717:
313:{\displaystyle Y}
289:{\displaystyle X}
269:{\displaystyle p}
245:{\displaystyle p}
191:
152:
76:
75:
68:
10089:
10026:
9989:
9961:
9955:
9949:
9946:
9940:
9934:
9928:
9922:
9913:
9907:
9840:
9838:
9837:
9832:
9830:
9829:
9826:
9813:
9811:
9810:
9805:
9803:
9802:
9799:
9786:
9784:
9783:
9778:
9776:
9775:
9756:
9754:
9753:
9748:
9746:
9745:
9729:
9727:
9726:
9721:
9719:
9718:
9687:
9685:
9684:
9679:
9677:
9676:
9656:
9654:
9653:
9648:
9633:
9631:
9630:
9625:
9623:
9622:
9619:
9606:
9604:
9603:
9598:
9596:
9595:
9590:
9579:
9566:
9564:
9563:
9558:
9539:
9537:
9536:
9531:
9529:
9523:
9515:
9505:
9503:
9502:
9497:
9495:
9494:
9491:
9478:
9476:
9475:
9470:
9468:
9467:
9462:
9459:
9449:
9447:
9446:
9441:
9439:
9430:
9420:
9418:
9417:
9412:
9410:
9409:
9406:
9393:
9391:
9390:
9385:
9373:
9371:
9370:
9365:
9363:
9362:
9359:
9346:
9344:
9343:
9338:
9336:
9335:
9332:
9316:
9314:
9313:
9308:
9302:
9297:
9284:
9279:
9264:
9263:
9247:
9245:
9244:
9239:
9237:
9236:
9233:
9218:
9216:
9215:
9210:
9180:
9179:
9167:
9166:
9163:
9153:
9148:
9128:
9126:
9125:
9120:
9118:
9117:
9093:
9091:
9090:
9085:
9083:
9082:
9052:
9051:
9048:
9035:
9033:
9032:
9027:
9025:
9024:
8994:
8993:
8990:
8977:
8975:
8974:
8969:
8967:
8966:
8936:
8935:
8932:
8914:
8913:
8910:
8894:
8892:
8891:
8886:
8881:
8880:
8859:
8858:
8834:
8833:
8811:
8809:
8808:
8803:
8801:
8800:
8784:
8782:
8781:
8776:
8764:
8762:
8761:
8756:
8754:
8753:
8737:
8735:
8734:
8729:
8727:
8726:
8721:
8718:
8708:
8706:
8705:
8700:
8668:
8660:
8631:
8623:
8606:
8605:
8602:
8584:
8583:
8580:
8562:
8561:
8536:
8534:
8533:
8528:
8526:
8525:
8520:
8517:
8507:
8505:
8504:
8499:
8487:
8485:
8484:
8479:
8468:of block length
8459:
8457:
8456:
8451:
8449:
8448:
8445:
8429:
8427:
8426:
8421:
8419:
8418:
8415:
8398:
8396:
8395:
8390:
8388:
8387:
8384:
8367:
8365:
8364:
8359:
8348:
8347:
8344:
8331:
8329:
8328:
8323:
8321:
8320:
8315:
8312:
8302:
8300:
8299:
8294:
8292:
8284:
8271:
8269:
8268:
8263:
8261:
8260:
8257:
8244:
8242:
8241:
8236:
8234:
8233:
8230:
8217:
8215:
8214:
8209:
8207:
8199:
8170:, and a rate of
8169:
8167:
8166:
8161:
8149:
8147:
8146:
8141:
8129:
8127:
8126:
8121:
8119:
8118:
8115:
8099:
8097:
8096:
8091:
8080:
8079:
8076:
8063:
8061:
8060:
8055:
8043:
8041:
8040:
8035:
8033:
8032:
8029:
8016:
8014:
8013:
8008:
8006:
8005:
8002:
7985:
7983:
7982:
7977:
7944:
7942:
7941:
7936:
7934:
7933:
7932:
7931:
7910:
7908:
7907:
7902:
7900:
7892:
7877:
7875:
7874:
7869:
7857:
7855:
7854:
7849:
7847:
7846:
7843:
7826:
7824:
7823:
7818:
7816:
7815:
7810:
7807:
7797:
7795:
7794:
7789:
7787:
7786:
7783:
7774:
7773:
7770:
7761:
7760:
7733:
7731:
7730:
7725:
7723:
7722:
7717:
7714:
7704:
7702:
7701:
7696:
7694:
7691:
7679:
7677:
7676:
7671:
7669:
7666:
7645:
7643:
7642:
7637:
7583:
7581:
7580:
7575:
7573:
7572:
7560:
7559:
7532:
7531:
7515:
7513:
7512:
7507:
7505:
7504:
7488:
7486:
7485:
7480:
7478:
7477:
7461:
7459:
7458:
7453:
7441:
7439:
7438:
7433:
7431:
7430:
7396:
7394:
7393:
7388:
7367:
7365:
7364:
7359:
7357:
7356:
7351:
7348:
7338:
7336:
7335:
7330:
7314:
7312:
7311:
7306:
7304:
7296:
7288:
7286:
7285:
7280:
7269:
7267:
7266:
7261:
7247:
7245:
7244:
7239:
7228:
7226:
7225:
7220:
7184:
7182:
7181:
7176:
7173:
7172:
7171:
7166:
7163:
7142:
7140:
7139:
7134:
7132:
7131:
7104:
7102:
7101:
7096:
7085:
7083:
7082:
7077:
7075:
7074:
7046:
7044:
7043:
7038:
7026:
7024:
7023:
7018:
7016:
7015:
6988:
6986:
6985:
6980:
6969:
6967:
6966:
6961:
6959:
6958:
6930:
6928:
6927:
6922:
6902:
6900:
6899:
6894:
6883:
6881:
6880:
6875:
6834:
6832:
6831:
6826:
6815:
6813:
6812:
6807:
6796:
6794:
6793:
6788:
6776:
6766:
6764:
6763:
6758:
6717:
6715:
6714:
6709:
6707:
6706:
6702:
6679:
6677:
6676:
6671:
6669:
6660:
6644:
6642:
6641:
6636:
6634:
6619:
6617:
6616:
6611:
6609:
6608:
6580:
6578:
6577:
6572:
6570:
6555:
6553:
6552:
6547:
6545:
6530:
6528:
6527:
6522:
6520:
6519:
6497:
6495:
6494:
6489:
6473:
6471:
6470:
6465:
6463:
6462:
6434:
6432:
6431:
6426:
6424:
6423:
6397:
6395:
6394:
6389:
6387:
6386:
6367:
6365:
6364:
6359:
6343:
6341:
6340:
6335:
6320:
6318:
6317:
6312:
6307:
6306:
6288:
6284:
6283:
6279:
6254:
6253:
6241:
6240:
6225:
6224:
6223:
6218:
6215:
6196:
6195:
6190:
6174:
6172:
6171:
6166:
6164:
6163:
6147:
6145:
6144:
6139:
6137:
6136:
6117:
6115:
6114:
6109:
6104:
6103:
6085:
6081:
6080:
6076:
6069:
6065:
6031:
6030:
6029:
6024:
6021:
6002:
6001:
5996:
5985:
5984:
5979:
5963:
5961:
5960:
5955:
5940:
5938:
5937:
5932:
5927:
5926:
5908:
5904:
5903:
5899:
5892:
5888:
5854:
5853:
5852:
5847:
5844:
5825:
5824:
5819:
5808:
5807:
5802:
5782:
5780:
5779:
5774:
5759:
5757:
5756:
5751:
5749:
5745:
5744:
5723:
5719:
5716:
5714:
5713:
5668:
5667:
5640:
5634:
5632:
5631:
5589:
5588:
5584:
5583:
5582:
5558:
5533:
5518:
5517:
5516:
5493:
5488:
5487:
5460:
5454:
5453:
5452:
5429:
5428:
5424:
5423:
5422:
5398:
5391:
5390:
5363:
5343:
5328:
5327:
5326:
5303:
5302:
5298:
5297:
5296:
5271:
5267:
5226:
5225:
5224:
5219:
5216:
5197:
5196:
5191:
5164:
5162:
5161:
5156:
5154:
5150:
5149:
5107:
5092:
5091:
5090:
5067:
5066:
5062:
5061:
5060:
5036:
5032:
5031:
4989:
4974:
4973:
4972:
4949:
4948:
4906:
4891:
4890:
4889:
4863:
4859:
4858:
4816:
4801:
4800:
4799:
4720:
4719:
4718:
4713:
4710:
4684:
4682:
4681:
4676:
4622:
4620:
4619:
4614:
4612:
4611:
4595:
4593:
4592:
4587:
4566:
4564:
4563:
4558:
4546:
4544:
4543:
4538:
4521:
4492:
4480:
4478:
4477:
4472:
4460:
4458:
4457:
4452:
4450:
4449:
4421:
4419:
4418:
4413:
4411:
4410:
4367:
4365:
4364:
4359:
4357:
4356:
4332:
4314:. Now using the
4313:
4311:
4310:
4305:
4303:
4302:
4272:
4271:
4262:
4257:
4256:
4228:
4226:
4225:
4220:
4218:
4217:
4154:
4151:
4142:
4140:
4139:
4134:
4108:
4105:
4096:
4094:
4093:
4088:
4076:
4074:
4073:
4068:
4056:
4054:
4053:
4048:
4021:
4019:
4018:
4013:
4011:
4010:
4001:
3960:
3957:
3948:
3946:
3945:
3940:
3899:
3875:
3873:
3872:
3867:
3855:
3853:
3852:
3847:
3832:
3830:
3829:
3824:
3819:
3818:
3814:
3813:
3812:
3737:
3736:
3735:
3734:
3729:
3726:
3691:
3689:
3688:
3683:
3645:
3612:
3610:
3609:
3604:
3602:
3601:
3577:
3559:
3557:
3556:
3551:
3530:
3528:
3527:
3522:
3495:
3493:
3492:
3487:
3472:
3470:
3469:
3464:
3452:
3450:
3449:
3444:
3423:
3421:
3420:
3415:
3400:
3398:
3397:
3392:
3387:
3383:
3342:
3341:
3340:
3335:
3332:
3313:
3312:
3307:
3292:
3290:
3289:
3284:
3264:
3262:
3261:
3256:
3254:
3253:
3219:
3217:
3216:
3211:
3199:
3197:
3196:
3191:
3172:
3162:
3160:
3159:
3154:
3142:
3140:
3139:
3134:
3118:
3116:
3115:
3110:
3108:
3107:
3102:
3099:
3089:
3087:
3086:
3081:
3069:
3067:
3066:
3061:
3059:
3058:
3024:
3022:
3021:
3016:
3004:
3002:
3001:
2996:
2984:
2982:
2981:
2976:
2945:
2943:
2942:
2937:
2925:
2923:
2922:
2917:
2881:Hamming distance
2878:
2876:
2875:
2870:
2868:
2867:
2833:
2831:
2830:
2825:
2823:
2822:
2788:
2786:
2785:
2780:
2778:
2777:
2753:
2752:
2718:
2716:
2715:
2710:
2698:
2696:
2695:
2690:
2688:
2687:
2644:
2642:
2641:
2636:
2634:
2633:
2599:
2597:
2596:
2591:
2589:
2588:
2564:
2563:
2517:
2515:
2514:
2509:
2497:
2495:
2494:
2489:
2487:
2486:
2481:
2478:
2468:
2466:
2465:
2460:
2448:
2446:
2445:
2440:
2438:
2437:
2402:
2400:
2399:
2394:
2392:
2391:
2387:
2331:
2330:
2329:
2324:
2321:
2295:
2293:
2292:
2287:
2285:
2284:
2250:
2248:
2247:
2242:
2240:
2239:
2215:
2214:
2180:
2178:
2177:
2172:
2170:
2169:
2145:
2144:
2110:
2108:
2107:
2102:
2048:
2046:
2045:
2040:
2028:
2026:
2025:
2020:
2008:
2006:
2005:
2000:
1988:
1986:
1985:
1980:
1972:
1963:
1941:
1939:
1938:
1933:
1928:
1919:
1903:
1893:
1891:
1890:
1885:
1883:
1882:
1877:
1874:
1858:
1856:
1855:
1850:
1832:
1830:
1829:
1824:
1812:
1810:
1809:
1804:
1792:
1790:
1789:
1784:
1768:
1766:
1765:
1760:
1758:
1757:
1752:
1749:
1739:
1737:
1736:
1731:
1716:
1714:
1713:
1708:
1706:
1705:
1700:
1697:
1669:
1667:
1666:
1661:
1647:
1646:
1643:
1628:
1627:
1624:
1611:
1609:
1608:
1603:
1592:
1591:
1575:
1573:
1572:
1567:
1546:
1544:
1543:
1538:
1526:
1524:
1523:
1518:
1507:
1506:
1490:
1488:
1487:
1482:
1458:
1456:
1455:
1450:
1436:
1408:
1406:
1405:
1400:
1398:
1379:
1378:
1375:
1348:
1332:
1331:
1328:
1322:
1312:
1311:
1300:
1252:
1248:
1235:
1212:
1211:
1200:
1152:
1142:
1071:
1069:
1068:
1063:
1061:
1057:
1030:
1020:
1019:
990:
988:
987:
982:
971:
970:
943:
937:
935:
934:
929:
927:
925:
911:
906:
905:
878:
870:
865:
864:
837:
836:
833:
813:
811:
810:
805:
791:
790:
787:
771:
769:
768:
763:
746:
745:
742:
727:
726:
723:
715:
699:channel capacity
672:
670:
669:
664:
659:
632:
630:
629:
624:
619:
598:
596:
595:
590:
585:
555:
553:
552:
547:
545:
513:
464:
415:
360:
319:
317:
316:
311:
295:
293:
292:
287:
275:
273:
272:
267:
252:, denoted by BSC
251:
249:
248:
243:
203:
201:
200:
195:
193:
192:
189:
176:
174:
173:
168:
154:
153:
150:
130:channel capacity
71:
64:
60:
57:
51:
46:this article by
37:inline citations
24:
23:
16:
10097:
10096:
10092:
10091:
10090:
10088:
10087:
10086:
10072:
10071:
10023:
9986:
9970:
9965:
9964:
9956:
9952:
9947:
9943:
9935:
9931:
9923:
9916:
9908:
9904:
9899:
9887:
9851:
9825:
9821:
9819:
9816:
9815:
9798:
9794:
9792:
9789:
9788:
9771:
9767:
9765:
9762:
9761:
9741:
9737:
9735:
9732:
9731:
9699:
9695:
9693:
9690:
9689:
9672:
9668:
9666:
9663:
9662:
9639:
9636:
9635:
9618:
9614:
9612:
9609:
9608:
9580:
9578:
9574:
9572:
9569:
9568:
9549:
9546:
9545:
9516:
9513:
9511:
9508:
9507:
9490:
9486:
9484:
9481:
9480:
9463:
9458:
9457:
9455:
9452:
9451:
9428:
9426:
9423:
9422:
9405:
9401:
9399:
9396:
9395:
9379:
9376:
9375:
9358:
9354:
9352:
9349:
9348:
9331:
9327:
9325:
9322:
9321:
9298:
9293:
9280:
9275:
9259:
9255:
9253:
9250:
9249:
9232:
9228:
9226:
9223:
9222:
9175:
9171:
9162:
9158:
9149:
9144:
9138:
9135:
9134:
9113:
9109:
9107:
9104:
9103:
9100:
9069:
9065:
9047:
9043:
9041:
9038:
9037:
9011:
9007:
8989:
8985:
8983:
8980:
8979:
8953:
8949:
8931:
8927:
8909:
8905:
8900:
8897:
8896:
8876:
8872:
8854:
8850:
8829:
8825:
8817:
8814:
8813:
8796:
8792:
8790:
8787:
8786:
8770:
8767:
8766:
8749:
8745:
8743:
8740:
8739:
8722:
8717:
8716:
8714:
8711:
8710:
8659:
8622:
8601:
8597:
8579:
8575:
8557:
8553:
8545:
8542:
8541:
8521:
8516:
8515:
8513:
8510:
8509:
8493:
8490:
8489:
8473:
8470:
8469:
8444:
8440:
8438:
8435:
8434:
8414:
8410:
8408:
8405:
8404:
8383:
8379:
8377:
8374:
8373:
8343:
8339:
8337:
8334:
8333:
8316:
8311:
8310:
8308:
8305:
8304:
8283:
8281:
8278:
8277:
8256:
8252:
8250:
8247:
8246:
8229:
8225:
8223:
8220:
8219:
8198:
8175:
8172:
8171:
8155:
8152:
8151:
8135:
8132:
8131:
8114:
8110:
8108:
8105:
8104:
8103:The inner code
8075:
8071:
8069:
8066:
8065:
8049:
8046:
8045:
8028:
8024:
8022:
8019:
8018:
8001:
7997:
7995:
7992:
7991:
7950:
7947:
7946:
7927:
7923:
7922:
7918:
7916:
7913:
7912:
7911:over the field
7891:
7883:
7880:
7879:
7863:
7860:
7859:
7842:
7838:
7836:
7833:
7832:
7831:The outer code
7827:. In his code,
7811:
7806:
7805:
7803:
7800:
7799:
7782:
7778:
7769:
7765:
7756:
7752:
7750:
7747:
7746:
7740:
7718:
7713:
7712:
7710:
7707:
7706:
7690:
7688:
7685:
7684:
7665:
7663:
7660:
7659:
7652:
7589:
7586:
7585:
7568:
7564:
7537:
7533:
7527:
7523:
7521:
7518:
7517:
7500:
7496:
7494:
7491:
7490:
7473:
7469:
7467:
7464:
7463:
7447:
7444:
7443:
7408:
7404:
7402:
7399:
7398:
7373:
7370:
7369:
7352:
7347:
7346:
7344:
7341:
7340:
7324:
7321:
7320:
7317:
7295:
7293:
7290:
7289:
7274:
7271:
7270:
7252:
7249:
7248:
7233:
7230:
7229:
7190:
7187:
7186:
7167:
7162:
7161:
7154:
7148:
7145:
7144:
7127:
7123:
7109:
7106:
7105:
7090:
7087:
7086:
7070:
7066:
7052:
7049:
7048:
7032:
7029:
7028:
7011:
7007:
6993:
6990:
6989:
6974:
6971:
6970:
6954:
6950:
6936:
6933:
6932:
6916:
6913:
6912:
6888:
6885:
6884:
6839:
6836:
6835:
6820:
6817:
6816:
6801:
6798:
6797:
6782:
6779:
6778:
6774:
6737:
6734:
6733:
6730:
6695:
6691:
6687:
6685:
6682:
6681:
6658:
6650:
6647:
6646:
6645:to be equal to
6627:
6625:
6622:
6621:
6592:
6588:
6586:
6583:
6582:
6563:
6561:
6558:
6557:
6538:
6536:
6533:
6532:
6509:
6505:
6503:
6500:
6499:
6483:
6480:
6479:
6452:
6448:
6440:
6437:
6436:
6413:
6409:
6407:
6404:
6403:
6382:
6378:
6376:
6373:
6372:
6353:
6350:
6349:
6329:
6326:
6325:
6296:
6292:
6249:
6245:
6236:
6232:
6231:
6227:
6219:
6214:
6213:
6206:
6201:
6197:
6191:
6186:
6185:
6183:
6180:
6179:
6159:
6155:
6153:
6150:
6149:
6132:
6128:
6126:
6123:
6122:
6093:
6089:
6037:
6033:
6025:
6020:
6019:
6012:
6007:
6003:
5997:
5992:
5991:
5990:
5986:
5980:
5975:
5974:
5972:
5969:
5968:
5949:
5946:
5945:
5916:
5912:
5860:
5856:
5848:
5843:
5842:
5835:
5830:
5826:
5820:
5815:
5814:
5813:
5809:
5803:
5798:
5797:
5795:
5792:
5791:
5768:
5765:
5764:
5747:
5746:
5734:
5730:
5721:
5720:
5715:
5679:
5675:
5648:
5644:
5636:
5633:
5597:
5593:
5578:
5574:
5573:
5569:
5565:
5556:
5555:
5529:
5512:
5508:
5501:
5492:
5468:
5464:
5456:
5448:
5444:
5437:
5418:
5414:
5413:
5409:
5405:
5396:
5395:
5371:
5367:
5359:
5339:
5322:
5318:
5311:
5292:
5288:
5287:
5283:
5279:
5272:
5220:
5215:
5214:
5207:
5202:
5198:
5192:
5187:
5186:
5182:
5180:
5177:
5176:
5152:
5151:
5130:
5126:
5103:
5086:
5082:
5075:
5056:
5052:
5051:
5047:
5043:
5034:
5033:
5012:
5008:
4985:
4968:
4964:
4957:
4929:
4925:
4902:
4885:
4881:
4874:
4861:
4860:
4839:
4835:
4812:
4795:
4791:
4772:
4761:
4714:
4709:
4708:
4701:
4693:
4691:
4688:
4687:
4628:
4625:
4624:
4607:
4603:
4601:
4598:
4597:
4572:
4569:
4568:
4552:
4549:
4548:
4517:
4506:
4503:
4502:
4466:
4463:
4462:
4433:
4429:
4427:
4424:
4423:
4382:
4378:
4373:
4370:
4369:
4352:
4348:
4325:
4323:
4320:
4319:
4280:
4276:
4267:
4263:
4258:
4240:
4236:
4234:
4231:
4230:
4201:
4197:
4150:
4148:
4145:
4144:
4104:
4102:
4099:
4098:
4082:
4079:
4078:
4062:
4059:
4058:
4027:
4024:
4023:
4006:
4002:
3997:
3956:
3954:
3951:
3950:
3892:
3884:
3881:
3880:
3861:
3858:
3857:
3841:
3838:
3837:
3808:
3804:
3803:
3799:
3795:
3730:
3725:
3724:
3717:
3713:
3708:
3705:
3704:
3638:
3618:
3615:
3614:
3597:
3593:
3570:
3568:
3565:
3564:
3536:
3533:
3532:
3501:
3498:
3497:
3481:
3478:
3477:
3458:
3455:
3454:
3429:
3426:
3425:
3409:
3406:
3405:
3336:
3331:
3330:
3323:
3318:
3314:
3308:
3303:
3302:
3300:
3297:
3296:
3278:
3275:
3274:
3249:
3245:
3225:
3222:
3221:
3205:
3202:
3201:
3185:
3182:
3181:
3148:
3145:
3144:
3128:
3125:
3124:
3103:
3098:
3097:
3095:
3092:
3091:
3075:
3072:
3071:
3054:
3050:
3030:
3027:
3026:
3010:
3007:
3006:
2990:
2987:
2986:
2958:
2955:
2954:
2931:
2928:
2927:
2887:
2884:
2883:
2863:
2859:
2839:
2836:
2835:
2818:
2814:
2794:
2791:
2790:
2773:
2769:
2748:
2744:
2724:
2721:
2720:
2704:
2701:
2700:
2683:
2679:
2650:
2647:
2646:
2629:
2625:
2605:
2602:
2601:
2584:
2580:
2559:
2555:
2535:
2532:
2531:
2524:
2503:
2500:
2499:
2482:
2477:
2476:
2474:
2471:
2470:
2454:
2451:
2450:
2433:
2429:
2415:
2412:
2411:
2408:
2383:
2379:
2375:
2325:
2320:
2319:
2312:
2306:
2303:
2302:
2280:
2276:
2256:
2253:
2252:
2235:
2231:
2210:
2206:
2186:
2183:
2182:
2165:
2161:
2140:
2136:
2116:
2113:
2112:
2054:
2051:
2050:
2034:
2031:
2030:
2014:
2011:
2010:
1994:
1991:
1990:
1961:
1947:
1944:
1943:
1917:
1909:
1906:
1905:
1901:
1878:
1873:
1872:
1864:
1861:
1860:
1838:
1835:
1834:
1818:
1815:
1814:
1798:
1795:
1794:
1778:
1775:
1774:
1771:random variable
1753:
1748:
1747:
1745:
1742:
1741:
1725:
1722:
1721:
1701:
1696:
1695:
1693:
1690:
1689:
1682:
1642:
1638:
1623:
1619:
1617:
1614:
1613:
1587:
1583:
1581:
1578:
1577:
1552:
1549:
1548:
1532:
1529:
1528:
1502:
1498:
1496:
1493:
1492:
1467:
1464:
1463:
1432:
1421:
1418:
1417:
1396:
1395:
1374:
1370:
1346:
1345:
1327:
1323:
1307:
1303:
1302:
1278:
1250:
1249:
1231:
1207:
1203:
1202:
1178:
1150:
1149:
1138:
1107:
1085:
1083:
1080:
1079:
1036:
1032:
1015:
1011:
1010:
998:
995:
994:
966:
962:
960:
957:
956:
915:
910:
901:
897:
869:
860:
856:
832:
828:
826:
823:
822:
786:
782:
780:
777:
776:
741:
737:
722:
718:
713:
710:
709:
679:
655:
638:
635:
634:
615:
604:
601:
600:
581:
564:
561:
560:
543:
542:
526:
509:
488:
487:
477:
460:
439:
438:
428:
411:
390:
389:
373:
356:
334:
332:
329:
328:
305:
302:
301:
298:random variable
281:
278:
277:
261:
258:
257:
255:
237:
234:
233:
214:
188:
184:
182:
179:
178:
149:
145:
137:
134:
133:
127:
87:
72:
61:
55:
52:
42:Please help to
41:
25:
21:
12:
11:
5:
10095:
10085:
10084:
10070:
10069:
10063:
10057:
10046:
10027:
10021:
10003:
9997:
9990:
9984:
9969:
9966:
9963:
9962:
9960:, p. 3–4.
9950:
9941:
9939:, p. 187.
9929:
9914:
9901:
9900:
9898:
9895:
9894:
9893:
9886:
9883:
9850:
9847:
9824:
9797:
9774:
9770:
9744:
9740:
9717:
9714:
9711:
9708:
9705:
9702:
9698:
9675:
9671:
9646:
9643:
9617:
9593:
9589:
9586:
9583:
9577:
9556:
9553:
9542:Chernoff bound
9526:
9522:
9519:
9489:
9466:
9436:
9433:
9404:
9383:
9357:
9330:
9318:
9317:
9306:
9301:
9296:
9292:
9288:
9283:
9278:
9274:
9270:
9267:
9262:
9258:
9231:
9219:
9208:
9205:
9202:
9199:
9196:
9193:
9190:
9186:
9183:
9178:
9174:
9170:
9161:
9157:
9152:
9147:
9143:
9116:
9112:
9099:
9096:
9081:
9078:
9075:
9072:
9068:
9064:
9061:
9058:
9055:
9046:
9023:
9020:
9017:
9014:
9010:
9006:
9003:
9000:
8997:
8988:
8965:
8962:
8959:
8956:
8952:
8948:
8945:
8942:
8939:
8930:
8926:
8923:
8920:
8917:
8908:
8904:
8884:
8879:
8875:
8871:
8868:
8865:
8862:
8857:
8853:
8849:
8846:
8843:
8840:
8837:
8832:
8828:
8824:
8821:
8799:
8795:
8774:
8752:
8748:
8725:
8698:
8695:
8692:
8689:
8686:
8683:
8680:
8677:
8674:
8671:
8666:
8663:
8658:
8655:
8652:
8649:
8646:
8643:
8640:
8637:
8634:
8629:
8626:
8621:
8618:
8615:
8612:
8609:
8600:
8596:
8593:
8590:
8587:
8578:
8574:
8571:
8568:
8565:
8560:
8556:
8552:
8549:
8524:
8497:
8488:and dimension
8477:
8443:
8413:
8382:
8370:
8369:
8357:
8354:
8351:
8342:
8319:
8290:
8287:
8255:
8228:
8205:
8202:
8197:
8194:
8191:
8188:
8185:
8182:
8179:
8159:
8139:
8113:
8101:
8089:
8086:
8083:
8074:
8053:
8027:
8000:
7975:
7972:
7969:
7966:
7963:
7960:
7957:
7954:
7930:
7926:
7921:
7898:
7895:
7890:
7887:
7867:
7841:
7814:
7781:
7777:
7768:
7764:
7759:
7755:
7739:
7736:
7721:
7651:
7648:
7635:
7632:
7629:
7626:
7623:
7620:
7617:
7614:
7611:
7608:
7605:
7602:
7599:
7596:
7593:
7571:
7567:
7563:
7558:
7555:
7552:
7549:
7546:
7543:
7540:
7536:
7530:
7526:
7503:
7499:
7476:
7472:
7451:
7429:
7426:
7423:
7420:
7417:
7414:
7411:
7407:
7386:
7383:
7380:
7377:
7355:
7328:
7302:
7299:
7278:
7259:
7256:
7237:
7218:
7215:
7212:
7209:
7206:
7203:
7200:
7197:
7194:
7170:
7160:
7157:
7153:
7143:respectively:
7130:
7126:
7122:
7119:
7116:
7113:
7094:
7073:
7069:
7065:
7062:
7059:
7056:
7036:
7014:
7010:
7006:
7003:
7000:
6997:
6978:
6957:
6953:
6949:
6946:
6943:
6940:
6920:
6892:
6873:
6870:
6867:
6864:
6861:
6858:
6855:
6852:
6849:
6846:
6843:
6824:
6805:
6786:
6769:
6756:
6753:
6750:
6747:
6744:
6741:
6729:
6726:
6725:
6724:
6721:
6720:
6705:
6701:
6698:
6694:
6690:
6666:
6663:
6657:
6654:
6633:
6630:
6607:
6604:
6601:
6598:
6595:
6591:
6569:
6566:
6544:
6541:
6518:
6515:
6512:
6508:
6487:
6461:
6458:
6455:
6451:
6447:
6444:
6422:
6419:
6416:
6412:
6385:
6381:
6369:simultaneously
6357:
6333:
6322:
6321:
6310:
6305:
6302:
6299:
6295:
6291:
6287:
6282:
6278:
6275:
6272:
6269:
6266:
6263:
6260:
6257:
6252:
6248:
6244:
6239:
6235:
6230:
6222:
6212:
6209:
6205:
6200:
6194:
6189:
6162:
6158:
6135:
6131:
6119:
6118:
6107:
6102:
6099:
6096:
6092:
6088:
6084:
6079:
6075:
6072:
6068:
6064:
6061:
6058:
6055:
6052:
6049:
6046:
6043:
6040:
6036:
6028:
6018:
6015:
6011:
6006:
6000:
5995:
5989:
5983:
5978:
5953:
5942:
5941:
5930:
5925:
5922:
5919:
5915:
5911:
5907:
5902:
5898:
5895:
5891:
5887:
5884:
5881:
5878:
5875:
5872:
5869:
5866:
5863:
5859:
5851:
5841:
5838:
5834:
5829:
5823:
5818:
5812:
5806:
5801:
5772:
5761:
5760:
5743:
5740:
5737:
5733:
5729:
5726:
5724:
5722:
5712:
5709:
5706:
5703:
5700:
5697:
5694:
5691:
5688:
5685:
5682:
5678:
5674:
5671:
5666:
5663:
5660:
5657:
5654:
5651:
5647:
5643:
5639:
5635:
5630:
5627:
5624:
5621:
5618:
5615:
5612:
5609:
5606:
5603:
5600:
5596:
5592:
5587:
5581:
5577:
5572:
5568:
5564:
5561:
5559:
5557:
5554:
5551:
5548:
5545:
5542:
5539:
5536:
5532:
5528:
5525:
5522:
5515:
5511:
5507:
5504:
5500:
5496:
5494:
5491:
5486:
5483:
5480:
5477:
5474:
5471:
5467:
5463:
5459:
5451:
5447:
5443:
5440:
5436:
5432:
5427:
5421:
5417:
5412:
5408:
5404:
5401:
5399:
5397:
5394:
5389:
5386:
5383:
5380:
5377:
5374:
5370:
5366:
5362:
5358:
5355:
5352:
5349:
5346:
5342:
5338:
5335:
5332:
5325:
5321:
5317:
5314:
5310:
5306:
5301:
5295:
5291:
5286:
5282:
5278:
5275:
5273:
5270:
5266:
5263:
5260:
5257:
5254:
5251:
5248:
5245:
5242:
5239:
5236:
5233:
5230:
5223:
5213:
5210:
5206:
5201:
5195:
5190:
5185:
5184:
5170:Chernoff bound
5166:
5165:
5148:
5145:
5142:
5139:
5136:
5133:
5129:
5125:
5122:
5119:
5116:
5113:
5110:
5106:
5102:
5099:
5096:
5089:
5085:
5081:
5078:
5074:
5070:
5065:
5059:
5055:
5050:
5046:
5042:
5039:
5037:
5035:
5030:
5027:
5024:
5021:
5018:
5015:
5011:
5007:
5004:
5001:
4998:
4995:
4992:
4988:
4984:
4981:
4978:
4971:
4967:
4963:
4960:
4956:
4952:
4947:
4944:
4941:
4938:
4935:
4932:
4928:
4924:
4921:
4918:
4915:
4912:
4909:
4905:
4901:
4898:
4895:
4888:
4884:
4880:
4877:
4873:
4869:
4866:
4864:
4862:
4857:
4854:
4851:
4848:
4845:
4842:
4838:
4834:
4831:
4828:
4825:
4822:
4819:
4815:
4811:
4808:
4805:
4798:
4794:
4790:
4787:
4784:
4781:
4778:
4775:
4771:
4767:
4764:
4762:
4760:
4757:
4754:
4751:
4748:
4745:
4742:
4739:
4736:
4733:
4730:
4727:
4724:
4717:
4707:
4704:
4700:
4696:
4695:
4674:
4671:
4668:
4665:
4662:
4659:
4656:
4653:
4650:
4647:
4644:
4641:
4638:
4635:
4632:
4610:
4606:
4596:was sent. Let
4585:
4582:
4579:
4576:
4556:
4536:
4533:
4530:
4527:
4524:
4520:
4516:
4513:
4510:
4497:
4496:
4488:
4487:
4484:
4483:
4470:
4448:
4445:
4442:
4439:
4436:
4432:
4409:
4406:
4403:
4400:
4397:
4394:
4391:
4388:
4385:
4381:
4377:
4355:
4351:
4347:
4344:
4341:
4338:
4335:
4331:
4328:
4301:
4298:
4295:
4292:
4289:
4286:
4283:
4279:
4275:
4270:
4266:
4261:
4255:
4252:
4249:
4246:
4243:
4239:
4216:
4213:
4210:
4207:
4204:
4200:
4196:
4193:
4190:
4187:
4184:
4181:
4178:
4175:
4172:
4169:
4166:
4163:
4160:
4157:
4132:
4129:
4126:
4123:
4120:
4117:
4114:
4111:
4086:
4066:
4046:
4043:
4040:
4037:
4034:
4031:
4009:
4005:
4000:
3996:
3993:
3990:
3987:
3984:
3981:
3978:
3975:
3972:
3969:
3966:
3963:
3938:
3935:
3932:
3929:
3926:
3923:
3920:
3917:
3914:
3911:
3908:
3905:
3902:
3898:
3895:
3891:
3888:
3865:
3845:
3834:
3833:
3822:
3817:
3811:
3807:
3802:
3798:
3794:
3791:
3788:
3785:
3782:
3779:
3776:
3773:
3770:
3767:
3764:
3761:
3758:
3755:
3752:
3749:
3746:
3743:
3740:
3733:
3723:
3720:
3716:
3712:
3698:Chernoff bound
3694:
3693:
3681:
3678:
3675:
3672:
3669:
3666:
3663:
3660:
3657:
3654:
3651:
3648:
3644:
3641:
3637:
3634:
3631:
3628:
3625:
3622:
3600:
3596:
3592:
3589:
3586:
3583:
3580:
3576:
3573:
3561:
3549:
3546:
3543:
3540:
3520:
3517:
3514:
3511:
3508:
3505:
3485:
3462:
3442:
3439:
3436:
3433:
3413:
3402:
3401:
3390:
3386:
3382:
3379:
3376:
3373:
3370:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3339:
3329:
3326:
3322:
3317:
3311:
3306:
3282:
3267:expected value
3252:
3248:
3244:
3241:
3238:
3235:
3232:
3229:
3209:
3189:
3177:
3176:
3152:
3132:
3106:
3079:
3057:
3053:
3049:
3046:
3043:
3040:
3037:
3034:
3014:
2994:
2974:
2971:
2968:
2965:
2962:
2935:
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2879:such that the
2866:
2862:
2858:
2855:
2852:
2849:
2846:
2843:
2821:
2817:
2813:
2810:
2807:
2804:
2801:
2798:
2776:
2772:
2768:
2765:
2762:
2759:
2756:
2751:
2747:
2743:
2740:
2737:
2734:
2731:
2728:
2708:
2686:
2682:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2632:
2628:
2624:
2621:
2618:
2615:
2612:
2609:
2587:
2583:
2579:
2576:
2573:
2570:
2567:
2562:
2558:
2554:
2551:
2548:
2545:
2542:
2539:
2523:
2520:
2507:
2485:
2458:
2436:
2432:
2428:
2425:
2422:
2419:
2407:
2406:
2405:
2404:
2390:
2386:
2382:
2378:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2328:
2318:
2315:
2311:
2283:
2279:
2275:
2272:
2269:
2266:
2263:
2260:
2238:
2234:
2230:
2227:
2224:
2221:
2218:
2213:
2209:
2205:
2202:
2199:
2196:
2193:
2190:
2168:
2164:
2160:
2157:
2154:
2151:
2148:
2143:
2139:
2135:
2132:
2129:
2126:
2123:
2120:
2100:
2097:
2094:
2091:
2088:
2085:
2082:
2079:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2038:
2018:
2009:(depending on
1998:
1978:
1975:
1969:
1966:
1960:
1957:
1954:
1951:
1931:
1925:
1922:
1916:
1913:
1896:
1881:
1871:
1868:
1848:
1845:
1842:
1822:
1802:
1782:
1756:
1729:
1704:
1681:
1678:
1677:
1676:
1673:
1672:
1659:
1656:
1653:
1650:
1641:
1637:
1634:
1631:
1622:
1601:
1598:
1595:
1590:
1586:
1565:
1562:
1559:
1556:
1536:
1516:
1513:
1510:
1505:
1501:
1480:
1477:
1474:
1471:
1448:
1445:
1442:
1439:
1435:
1431:
1428:
1425:
1410:
1409:
1394:
1391:
1388:
1385:
1382:
1373:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1349:
1347:
1344:
1341:
1338:
1335:
1326:
1321:
1318:
1315:
1310:
1306:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1277:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1253:
1251:
1247:
1244:
1241:
1238:
1234:
1230:
1227:
1224:
1221:
1218:
1215:
1210:
1206:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1177:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1153:
1151:
1148:
1145:
1141:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1108:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1087:
1073:
1072:
1060:
1055:
1052:
1049:
1046:
1043:
1040:
1035:
1029:
1026:
1023:
1018:
1014:
1009:
1005:
1002:
980:
977:
974:
969:
965:
948:
947:
939:
938:
924:
921:
918:
914:
909:
904:
900:
896:
893:
890:
887:
884:
881:
876:
873:
868:
863:
859:
855:
852:
849:
846:
843:
840:
831:
818:, defined by:
803:
800:
797:
794:
785:
773:
772:
761:
758:
755:
752:
749:
740:
736:
733:
730:
721:
678:
675:
662:
658:
654:
651:
648:
645:
642:
622:
618:
614:
611:
608:
588:
584:
580:
577:
574:
571:
568:
557:
556:
541:
538:
535:
532:
529:
527:
525:
522:
519:
516:
512:
508:
505:
502:
499:
496:
493:
490:
489:
486:
483:
480:
478:
476:
473:
470:
467:
463:
459:
456:
453:
450:
447:
444:
441:
440:
437:
434:
431:
429:
427:
424:
421:
418:
414:
410:
407:
404:
401:
398:
395:
392:
391:
388:
385:
382:
379:
376:
374:
372:
369:
366:
363:
359:
355:
352:
349:
346:
343:
340:
337:
336:
309:
285:
276:. That is, if
265:
253:
241:
213:
210:
187:
166:
163:
160:
157:
148:
144:
141:
125:
124:applies to BSC
93:model used in
89:) is a common
85:
74:
73:
28:
26:
19:
9:
6:
4:
3:
2:
10094:
10083:
10082:Coding theory
10080:
10079:
10077:
10067:
10064:
10061:
10058:
10055:
10051:
10047:
10044:
10040:
10036:
10032:
10028:
10024:
10022:0-521-64298-1
10018:
10014:
10013:
10008:
10004:
10001:
9998:
9995:
9991:
9987:
9981:
9977:
9972:
9971:
9959:
9958:MacKay (2003)
9954:
9945:
9938:
9933:
9927:, p. 15.
9926:
9925:MacKay (2003)
9921:
9919:
9911:
9910:MacKay (2003)
9906:
9902:
9892:
9889:
9888:
9882:
9880:
9876:
9872:
9867:
9865:
9861:
9860:cell division
9856:
9846:
9844:
9822:
9795:
9772:
9768:
9758:
9742:
9738:
9712:
9709:
9700:
9696:
9673:
9669:
9660:
9644:
9641:
9615:
9591:
9587:
9584:
9581:
9575:
9554:
9551:
9543:
9524:
9520:
9517:
9487:
9464:
9434:
9431:
9402:
9381:
9355:
9328:
9294:
9290:
9286:
9276:
9272:
9265:
9256:
9229:
9220:
9203:
9200:
9197:
9191:
9188:
9184:
9176:
9172:
9159:
9155:
9145:
9141:
9132:
9131:
9130:
9114:
9110:
9095:
9076:
9070:
9066:
9062:
9056:
9044:
9018:
9012:
9008:
9004:
8998:
8986:
8960:
8954:
8950:
8946:
8940:
8928:
8924:
8918:
8906:
8902:
8877:
8873:
8866:
8863:
8855:
8851:
8847:
8841:
8838:
8830:
8826:
8819:
8797:
8793:
8772:
8750:
8746:
8723:
8696:
8693:
8687:
8681:
8678:
8675:
8672:
8664:
8661:
8656:
8650:
8644:
8641:
8638:
8627:
8624:
8619:
8616:
8610:
8598:
8591:
8588:
8576:
8569:
8566:
8558:
8554:
8547:
8538:
8522:
8495:
8475:
8467:
8463:
8441:
8431:
8411:
8402:
8380:
8352:
8340:
8317:
8288:
8285:
8275:
8253:
8226:
8203:
8200:
8195:
8189:
8183:
8180:
8177:
8157:
8137:
8111:
8102:
8084:
8072:
8051:
8025:
7998:
7989:
7970:
7967:
7964:
7958:
7955:
7952:
7928:
7924:
7919:
7896:
7893:
7888:
7885:
7865:
7839:
7830:
7829:
7828:
7812:
7779:
7775:
7766:
7762:
7757:
7753:
7745:
7738:Forney's code
7735:
7719:
7683:
7656:
7647:
7627:
7621:
7618:
7615:
7609:
7606:
7603:
7594:
7591:
7569:
7565:
7561:
7556:
7550:
7547:
7544:
7538:
7534:
7528:
7524:
7501:
7497:
7474:
7470:
7449:
7427:
7421:
7418:
7415:
7409:
7405:
7381:
7375:
7353:
7326:
7316:
7300:
7297:
7276:
7254:
7235:
7213:
7210:
7204:
7198:
7192:
7168:
7158:
7155:
7128:
7120:
7117:
7114:
7071:
7063:
7060:
7057:
7034:
7012:
7004:
7001:
6998:
6955:
6947:
6944:
6941:
6918:
6910:
6906:
6868:
6862:
6859:
6856:
6850:
6847:
6844:
6803:
6784:
6768:
6751:
6745:
6742:
6739:
6719:
6703:
6699:
6696:
6692:
6688:
6664:
6661:
6655:
6652:
6631:
6628:
6605:
6602:
6599:
6596:
6593:
6589:
6567:
6564:
6542:
6539:
6516:
6513:
6510:
6506:
6485:
6477:
6459:
6456:
6453:
6449:
6445:
6442:
6420:
6417:
6414:
6410:
6401:
6383:
6379:
6370:
6355:
6348:the messages
6347:
6331:
6308:
6303:
6300:
6297:
6293:
6289:
6285:
6280:
6276:
6273:
6267:
6264:
6258:
6250:
6246:
6237:
6233:
6228:
6220:
6210:
6207:
6198:
6192:
6178:
6177:
6176:
6160:
6156:
6133:
6129:
6105:
6100:
6097:
6094:
6090:
6086:
6082:
6077:
6073:
6070:
6066:
6059:
6056:
6050:
6044:
6038:
6034:
6026:
6016:
6013:
6004:
5998:
5987:
5981:
5967:
5966:
5965:
5951:
5928:
5923:
5920:
5917:
5913:
5909:
5905:
5900:
5896:
5893:
5889:
5882:
5879:
5873:
5867:
5861:
5857:
5849:
5839:
5836:
5827:
5821:
5810:
5804:
5790:
5789:
5788:
5786:
5770:
5741:
5738:
5735:
5731:
5727:
5725:
5710:
5707:
5704:
5698:
5695:
5692:
5686:
5683:
5680:
5676:
5672:
5664:
5661:
5655:
5649:
5645:
5628:
5625:
5622:
5616:
5613:
5610:
5604:
5601:
5598:
5594:
5590:
5585:
5579:
5575:
5570:
5566:
5562:
5560:
5552:
5549:
5540:
5534:
5526:
5520:
5513:
5509:
5505:
5502:
5498:
5495:
5484:
5481:
5475:
5469:
5465:
5449:
5445:
5441:
5438:
5434:
5430:
5425:
5419:
5415:
5410:
5406:
5402:
5400:
5387:
5384:
5378:
5372:
5368:
5350:
5344:
5336:
5330:
5323:
5319:
5315:
5312:
5308:
5304:
5299:
5293:
5289:
5284:
5280:
5276:
5274:
5268:
5261:
5258:
5252:
5249:
5243:
5237:
5231:
5221:
5211:
5208:
5199:
5193:
5175:
5174:
5173:
5171:
5146:
5143:
5137:
5131:
5127:
5123:
5114:
5108:
5100:
5094:
5087:
5083:
5079:
5076:
5072:
5068:
5063:
5057:
5053:
5048:
5044:
5040:
5038:
5028:
5025:
5019:
5013:
5009:
5005:
4996:
4990:
4982:
4976:
4969:
4965:
4961:
4958:
4954:
4950:
4945:
4942:
4936:
4930:
4926:
4922:
4913:
4907:
4899:
4893:
4886:
4882:
4878:
4875:
4871:
4867:
4865:
4855:
4852:
4846:
4840:
4836:
4832:
4823:
4817:
4809:
4803:
4796:
4788:
4785:
4782:
4776:
4773:
4769:
4765:
4763:
4755:
4752:
4746:
4743:
4737:
4731:
4725:
4715:
4705:
4702:
4686:
4685:
4672:
4666:
4660:
4657:
4654:
4648:
4642:
4636:
4630:
4608:
4604:
4580:
4574:
4554:
4528:
4522:
4514:
4508:
4499:
4498:
4494:
4493:
4490:
4489:
4482:
4468:
4443:
4434:
4430:
4407:
4404:
4401:
4395:
4389:
4386:
4383:
4379:
4375:
4353:
4345:
4342:
4339:
4333:
4329:
4326:
4317:
4299:
4296:
4293:
4287:
4281:
4277:
4273:
4268:
4264:
4259:
4253:
4247:
4241:
4237:
4214:
4208:
4202:
4198:
4194:
4185:
4179:
4176:
4173:
4167:
4164:
4158:
4124:
4121:
4118:
4112:
4084:
4064:
4041:
4038:
4035:
4029:
4007:
4003:
3998:
3991:
3985:
3982:
3979:
3973:
3970:
3964:
3933:
3927:
3924:
3921:
3915:
3912:
3906:
3903:
3896:
3893:
3886:
3877:
3863:
3856:(recall that
3843:
3820:
3815:
3809:
3805:
3800:
3796:
3792:
3786:
3780:
3777:
3774:
3768:
3759:
3753:
3750:
3747:
3731:
3721:
3718:
3714:
3710:
3703:
3702:
3701:
3699:
3673:
3667:
3664:
3661:
3652:
3642:
3639:
3632:
3629:
3626:
3598:
3590:
3587:
3584:
3578:
3574:
3571:
3562:
3544:
3538:
3518:
3512:
3509:
3506:
3483:
3476:
3475:
3474:
3460:
3437:
3431:
3411:
3388:
3384:
3377:
3374:
3368:
3365:
3359:
3353:
3347:
3337:
3327:
3324:
3315:
3309:
3295:
3294:
3280:
3272:
3268:
3250:
3242:
3239:
3236:
3230:
3227:
3207:
3187:
3179:
3178:
3174:
3173:
3170:
3169:
3168:
3166:
3150:
3130:
3122:
3104:
3077:
3055:
3047:
3044:
3041:
3035:
3032:
3012:
2992:
2969:
2966:
2963:
2951:
2949:
2933:
2907:
2901:
2898:
2895:
2882:
2864:
2856:
2853:
2850:
2844:
2841:
2819:
2811:
2808:
2805:
2799:
2796:
2774:
2766:
2763:
2760:
2749:
2741:
2738:
2735:
2729:
2726:
2706:
2684:
2676:
2673:
2670:
2664:
2658:
2652:
2630:
2622:
2619:
2616:
2610:
2607:
2585:
2577:
2574:
2571:
2560:
2552:
2549:
2546:
2540:
2537:
2529:
2519:
2505:
2483:
2456:
2434:
2426:
2423:
2420:
2388:
2384:
2380:
2376:
2372:
2366:
2363:
2357:
2354:
2348:
2342:
2336:
2326:
2316:
2313:
2301:
2300:
2299:
2298:
2297:
2281:
2273:
2270:
2267:
2261:
2258:
2236:
2228:
2225:
2222:
2211:
2203:
2200:
2197:
2191:
2188:
2166:
2158:
2155:
2152:
2141:
2133:
2130:
2127:
2121:
2118:
2095:
2086:
2083:
2080:
2074:
2071:
2068:
2059:
2056:
2036:
2016:
1996:
1976:
1973:
1967:
1964:
1958:
1955:
1952:
1949:
1929:
1923:
1920:
1914:
1911:
1895:
1879:
1869:
1866:
1846:
1843:
1840:
1820:
1800:
1780:
1772:
1754:
1727:
1718:
1702:
1687:
1671:
1654:
1648:
1635:
1632:
1629:
1620:
1596:
1588:
1584:
1560:
1554:
1534:
1511:
1503:
1499:
1475:
1469:
1460:
1443:
1440:
1437:
1429:
1423:
1415:
1392:
1386:
1380:
1367:
1361:
1355:
1352:
1350:
1339:
1333:
1316:
1308:
1304:
1294:
1291:
1288:
1282:
1279:
1275:
1271:
1265:
1259:
1256:
1254:
1242:
1239:
1236:
1228:
1222:
1216:
1208:
1204:
1194:
1191:
1188:
1182:
1179:
1175:
1171:
1165:
1159:
1156:
1154:
1143:
1135:
1129:
1126:
1120:
1114:
1111:
1109:
1101:
1098:
1095:
1089:
1078:
1077:
1076:
1058:
1050:
1047:
1044:
1038:
1033:
1024:
1016:
1012:
1003:
1000:
993:
992:
975:
967:
963:
954:
950:
949:
945:
944:
941:
940:
922:
919:
916:
912:
907:
902:
898:
891:
888:
885:
879:
874:
871:
866:
861:
857:
853:
850:
844:
838:
821:
820:
819:
817:
798:
792:
759:
753:
747:
734:
731:
728:
719:
708:
707:
706:
704:
700:
692:
688:
683:
674:
660:
656:
652:
649:
646:
643:
640:
620:
616:
612:
609:
606:
586:
582:
578:
575:
572:
569:
566:
539:
536:
533:
530:
528:
520:
517:
514:
506:
503:
500:
494:
491:
484:
481:
479:
471:
468:
465:
457:
454:
451:
445:
442:
435:
432:
430:
422:
419:
416:
408:
405:
402:
396:
393:
386:
383:
380:
377:
375:
367:
364:
361:
353:
350:
347:
341:
338:
327:
326:
325:
323:
307:
299:
283:
263:
239:
227:
223:
218:
209:
207:
161:
155:
142:
139:
131:
123:
118:
116:
112:
108:
104:
100:
96:
95:coding theory
92:
88:
81:
70:
67:
59:
49:
45:
39:
38:
32:
27:
18:
17:
10011:
9975:
9953:
9944:
9932:
9912:, p. 4.
9905:
9868:
9852:
9849:Applications
9759:
9319:
9101:
8539:
8432:
8403:is used for
8371:
8332:and runs in
8150:, dimension
7741:
7657:
7653:
7318:
6770:
6731:
6475:
6368:
6345:
6323:
6120:
5943:
5784:
5762:
5167:
3878:
3835:
3695:
3531:centered at
3403:
3164:
3120:
2952:
2946:is called a
2645:, the value
2525:
2409:
1897:
1719:
1683:
1461:
1411:
1074:
774:
696:
690:
686:
558:
231:
225:
221:
177:bits, where
119:
110:
83:
79:
77:
62:
53:
34:
9506:is at most
9421:is at most
8978:as long as
8812:takes time
8466:linear code
8462:linear code
4316:union bound
3876:is fixed).
3271:probability
2950:function.)
2049:), and all
107:probability
48:introducing
9968:References
9855:disk drive
8460:we find a
7990:algorithm
6175:such that
3613:such that
1720:The noise
1684:Shannon's
212:Definition
115:disk drive
56:March 2013
31:references
9891:Z channel
9773:∗
9743:∗
9710:γ
9704:Ω
9701:−
9674:∗
9642:γ
9585:γ
9582:−
9552:γ
9518:γ
9432:γ
9300:′
9287:…
9282:′
9261:′
9192:∈
9151:′
9115:∗
8798:∗
8751:∗
8697:ϵ
8694:−
8679:−
8673:≥
8662:ϵ
8657:−
8642:−
8625:ϵ
8620:−
8589:×
8559:∗
8540:The rate
8286:γ
8201:ϵ
8196:−
8181:−
8052:γ
7968:
7894:ϵ
7889:−
7878:and rate
7776:∘
7758:∗
7655:correct.
7634:⌉
7622:ϵ
7607:−
7598:⌈
7595:≥
7562:≥
7551:ϵ
7422:ϵ
7277:≥
7236:≠
7159:∈
7093:→
6977:→
6911:function
6891:⌉
6863:ϵ
6848:−
6823:⌈
6804:≥
6743:−
6697:δ
6693:−
6656:−
6653:δ
6629:δ
6597:δ
6594:−
6514:−
6457:δ
6454:−
6446:⋅
6418:−
6301:δ
6298:−
6290:⩽
6274:≠
6251:∗
6238:∗
6211:∈
6161:∗
6134:∗
6098:δ
6095:−
6087:⩽
6071:≠
6017:∈
5964:. Hence:
5921:δ
5918:−
5910:⩽
5894:≠
5840:∈
5771:δ
5739:δ
5736:−
5728:⩽
5708:−
5699:ϵ
5673:⩽
5662:≠
5626:−
5617:ϵ
5576:ϵ
5571:−
5563:⩽
5550:⩽
5506:∈
5499:∑
5482:≠
5442:∈
5435:∑
5416:ϵ
5411:−
5403:⩽
5385:≠
5316:∈
5309:∑
5290:ϵ
5285:−
5277:⩽
5259:≠
5212:∈
5144:≠
5124:⋅
5080:∈
5073:∑
5054:ϵ
5049:−
5041:⩽
5026:≠
5006:⋅
4962:∈
4955:∑
4943:≠
4923:⋅
4879:∉
4872:∑
4868:⩽
4853:≠
4833:⋅
4777:∈
4770:∑
4753:≠
4706:∈
4661:ϵ
4438:Ω
4435:−
4422:which is
4405:−
4376:≤
4334:∈
4297:−
4195:≈
4180:ϵ
3986:ϵ
3928:ϵ
3904:∈
3864:ϵ
3806:ϵ
3801:−
3793:⩽
3781:ϵ
3742:Δ
3722:∈
3656:Δ
3653:⩽
3621:Δ
3579:∈
3513:ϵ
3375:≠
3328:∈
3231:∈
3208:ϵ
3036:∈
3013:ϵ
2890:Δ
2845:∈
2800:∈
2755:→
2665:∈
2611:∈
2566:→
2385:δ
2381:−
2373:≤
2364:≠
2317:∈
2262:∈
2217:→
2147:→
2099:⌋
2087:ϵ
2072:−
2063:⌊
2060:≤
2037:ϵ
1974:−
1956:ϵ
1870:∈
1844:−
1649:
1636:−
1381:
1368:−
1334:
1283:∈
1276:∑
1272:−
1183:∈
1176:∑
1172:−
1127:−
920:−
908:
889:−
867:
839:
793:
748:
735:−
650:≤
644:−
576:≤
570:≤
537:−
495:
446:
397:
384:−
342:
156:
143:−
117:storage.
10076:Category
10009:(2003).
9885:See also
9659:decoding
9221:Execute
8274:decoding
7988:decoding
6909:decoding
6905:encoding
6700:′
6632:′
6568:′
6543:′
6478:message
4330:′
3897:′
3643:′
3575:′
1904:For all
677:Capacity
9879:reduced
9877:can be
9133:Assume
9129:is to:
8272:with a
7680:or the
6772:Theorem
4623:denote
3269:of the
1899:Theorem
814:is the
693:-axis).
204:is the
44:improve
10041:, and
10019:
9982:
9036:; and
7945:, and
4022:where
1813:and a
946:Proof
775:where
716:
705:, is:
33:, but
9897:Notes
9871:noisy
8368:time.
8303:over
8100:time.
7650:Codes
6476:every
2522:Proof
1769:is a
599:. If
109:" of
10052:and
10017:ISBN
9980:ISBN
9843:LDPC
9814:and
9394:for
8245:for
8017:for
7027:and
6907:and
5785:each
4097:and
3769:>
3404:Let
3200:and
3180:Fix
3070:and
3005:and
2181:and
2029:and
1959:<
1953:<
1942:all
1915:<
703:bits
697:The
610:>
300:and
120:The
97:and
82:(or
10033:,
9864:DNA
9827:out
9620:out
9460:BSC
9360:out
9248:on
9234:out
8991:out
8933:out
8719:BSC
8603:out
8518:BSC
8416:out
8385:out
8313:BSC
8077:out
8030:out
8003:out
7965:log
7844:out
7808:BSC
7771:out
7715:BSC
7692:BEC
7667:BSC
7349:BSC
7164:BSC
6777:If
6346:all
6216:BSC
6022:BSC
5845:BSC
5217:BSC
4711:BSC
4368:by
4152:Vol
4106:Vol
3958:Vol
3949:is
3727:BSC
3333:BSC
3100:BSC
2479:BSC
2322:BSC
1894:".
1875:BSC
1750:BSC
1698:BSC
1625:BSC
1008:max
899:log
858:log
724:BSC
103:bit
84:BSC
10078::
10043:30
10039:29
10037:,
10035:10
9917:^
9800:in
9492:in
9407:in
9333:in
9164:in
9094:.
9049:in
8911:in
8581:in
8446:in
8430:.
8345:in
8258:in
8231:in
8116:in
7784:in
7315:.
7152:Pr
7047::
6931::
6204:Pr
6010:Pr
5833:Pr
5205:Pr
4699:Pr
4481:.
3321:Pr
3167:.
2310:Pr
1717:.
1670:.
991::
673:.
492:Pr
443:Pr
394:Pr
339:Pr
324::
78:A
10056:.
10054:2
10050:1
10045:.
10031:9
10025:.
9988:.
9823:C
9796:C
9769:C
9739:C
9716:)
9713:N
9707:(
9697:2
9670:C
9645:N
9616:C
9592:6
9588:N
9576:e
9555:N
9525:2
9521:N
9488:D
9465:p
9435:2
9403:D
9382:i
9356:C
9329:C
9305:)
9295:N
9291:y
9277:1
9273:y
9269:(
9266:=
9257:y
9230:D
9207:)
9204:N
9201:,
9198:0
9195:(
9189:i
9185:,
9182:)
9177:i
9173:y
9169:(
9160:D
9156:=
9146:i
9142:y
9111:C
9080:)
9077:k
9074:(
9071:O
9067:2
9063:=
9060:)
9057:k
9054:(
9045:t
9022:)
9019:1
9016:(
9013:O
9009:N
9005:=
9002:)
8999:N
8996:(
8987:t
8964:)
8961:1
8958:(
8955:O
8951:N
8947:=
8944:)
8941:N
8938:(
8929:t
8925:+
8922:)
8919:k
8916:(
8907:t
8903:N
8883:)
8878:2
8874:N
8870:(
8867:O
8864:=
8861:)
8856:2
8852:k
8848:N
8845:(
8842:O
8839:+
8836:)
8831:2
8827:N
8823:(
8820:O
8794:C
8773:N
8747:C
8724:p
8691:)
8688:p
8685:(
8682:H
8676:1
8670:)
8665:2
8654:)
8651:p
8648:(
8645:H
8639:1
8636:(
8633:)
8628:2
8617:1
8614:(
8611:=
8608:)
8599:C
8595:(
8592:R
8586:)
8577:C
8573:(
8570:R
8567:=
8564:)
8555:C
8551:(
8548:R
8523:p
8496:k
8476:n
8442:C
8412:C
8381:C
8356:)
8353:N
8350:(
8341:t
8318:p
8289:2
8254:C
8227:D
8204:2
8193:)
8190:p
8187:(
8184:H
8178:1
8158:k
8138:n
8112:C
8088:)
8085:N
8082:(
8073:t
8026:C
7999:D
7974:)
7971:N
7962:(
7959:O
7956:=
7953:k
7929:k
7925:2
7920:F
7897:2
7886:1
7866:N
7840:C
7813:p
7780:C
7767:C
7763:=
7754:C
7720:p
7631:)
7628:n
7625:)
7619:+
7616:p
7613:(
7610:H
7604:1
7601:(
7592:k
7570:n
7566:2
7557:n
7554:)
7548:+
7545:p
7542:(
7539:H
7535:2
7529:k
7525:2
7502:n
7498:2
7475:k
7471:2
7450:n
7428:n
7425:)
7419:+
7416:p
7413:(
7410:H
7406:2
7385:)
7382:p
7379:(
7376:H
7354:p
7327:k
7301:2
7298:1
7258:]
7255:m
7217:)
7214:e
7211:+
7208:)
7205:m
7202:(
7199:E
7196:(
7193:D
7185:[
7169:p
7156:e
7129:k
7125:}
7121:1
7118:,
7115:0
7112:{
7072:n
7068:}
7064:1
7061:,
7058:0
7055:{
7035:D
7013:n
7009:}
7005:1
7002:,
6999:0
6996:{
6956:k
6952:}
6948:1
6945:,
6942:0
6939:{
6919:E
6872:)
6869:n
6866:)
6860:+
6857:p
6854:(
6851:H
6845:1
6842:(
6785:k
6755:)
6752:p
6749:(
6746:H
6740:1
6704:n
6689:2
6665:n
6662:1
6606:1
6603:+
6600:n
6590:2
6565:D
6540:E
6517:1
6511:k
6507:2
6486:m
6460:n
6450:2
6443:2
6421:1
6415:k
6411:2
6384:k
6380:2
6356:m
6332:m
6309:.
6304:n
6294:2
6286:]
6281:]
6277:m
6271:)
6268:e
6265:+
6262:)
6259:m
6256:(
6247:E
6243:(
6234:D
6229:[
6221:p
6208:e
6199:[
6193:m
6188:E
6157:D
6130:E
6106:.
6101:n
6091:2
6083:]
6078:]
6074:m
6067:]
6063:)
6060:e
6057:+
6054:)
6051:m
6048:(
6045:E
6042:(
6039:D
6035:[
6027:p
6014:e
6005:[
5999:m
5994:E
5988:[
5982:E
5977:E
5952:E
5929:.
5924:n
5914:2
5906:]
5901:]
5897:m
5890:]
5886:)
5883:e
5880:+
5877:)
5874:m
5871:(
5868:E
5865:(
5862:D
5858:[
5850:p
5837:e
5828:[
5822:E
5817:E
5811:[
5805:m
5800:E
5742:n
5732:2
5711:n
5705:n
5702:)
5696:+
5693:p
5690:(
5687:H
5684:+
5681:k
5677:2
5670:]
5665:m
5659:)
5656:y
5653:(
5650:D
5646:1
5642:[
5638:E
5629:n
5623:n
5620:)
5614:+
5611:p
5608:(
5605:H
5602:+
5599:k
5595:2
5591:+
5586:n
5580:2
5567:2
5553:1
5547:)
5544:)
5541:m
5538:(
5535:E
5531:|
5527:y
5524:(
5521:p
5514:0
5510:B
5503:y
5490:]
5485:m
5479:)
5476:y
5473:(
5470:D
5466:1
5462:[
5458:E
5450:0
5446:B
5439:y
5431:+
5426:n
5420:2
5407:2
5393:]
5388:m
5382:)
5379:y
5376:(
5373:D
5369:1
5365:[
5361:E
5357:)
5354:)
5351:m
5348:(
5345:E
5341:|
5337:y
5334:(
5331:p
5324:0
5320:B
5313:y
5305:+
5300:n
5294:2
5281:2
5269:]
5265:]
5262:m
5256:)
5253:e
5250:+
5247:)
5244:m
5241:(
5238:E
5235:(
5232:D
5229:[
5222:p
5209:e
5200:[
5194:E
5189:E
5147:m
5141:)
5138:y
5135:(
5132:D
5128:1
5121:)
5118:)
5115:m
5112:(
5109:E
5105:|
5101:y
5098:(
5095:p
5088:0
5084:B
5077:y
5069:+
5064:n
5058:2
5045:2
5029:m
5023:)
5020:y
5017:(
5014:D
5010:1
5003:)
5000:)
4997:m
4994:(
4991:E
4987:|
4983:y
4980:(
4977:p
4970:0
4966:B
4959:y
4951:+
4946:m
4940:)
4937:y
4934:(
4931:D
4927:1
4920:)
4917:)
4914:m
4911:(
4908:E
4904:|
4900:y
4897:(
4894:p
4887:0
4883:B
4876:y
4856:m
4850:)
4847:y
4844:(
4841:D
4837:1
4830:)
4827:)
4824:m
4821:(
4818:E
4814:|
4810:y
4807:(
4804:p
4797:n
4793:}
4789:1
4786:,
4783:0
4780:{
4774:y
4766:=
4759:]
4756:m
4750:)
4747:e
4744:+
4741:)
4738:m
4735:(
4732:E
4729:(
4726:D
4723:[
4716:p
4703:e
4673:.
4670:)
4667:n
4664:)
4658:+
4655:p
4652:(
4649:,
4646:)
4643:m
4640:(
4637:E
4634:(
4631:B
4609:0
4605:B
4584:)
4581:m
4578:(
4575:E
4555:y
4535:)
4532:)
4529:m
4526:(
4523:E
4519:|
4515:y
4512:(
4509:p
4469:k
4447:)
4444:n
4441:(
4431:2
4408:n
4402:n
4399:)
4396:p
4393:(
4390:H
4387:+
4384:k
4380:2
4354:k
4350:}
4346:1
4343:,
4340:0
4337:{
4327:m
4300:n
4294:n
4291:)
4288:p
4285:(
4282:H
4278:2
4274:=
4269:n
4265:2
4260:/
4254:n
4251:)
4248:p
4245:(
4242:H
4238:2
4215:n
4212:)
4209:p
4206:(
4203:H
4199:2
4192:)
4189:)
4186:n
4183:)
4177:+
4174:p
4171:(
4168:,
4165:y
4162:(
4159:B
4156:(
4131:)
4128:)
4125:r
4122:,
4119:x
4116:(
4113:B
4110:(
4085:x
4065:r
4045:)
4042:r
4039:,
4036:x
4033:(
4030:B
4008:n
4004:2
3999:/
3995:)
3992:n
3989:)
3983:+
3980:p
3977:(
3974:,
3971:y
3968:(
3965:B
3962:(
3937:)
3934:n
3931:)
3925:+
3922:p
3919:(
3916:,
3913:y
3910:(
3907:B
3901:)
3894:m
3890:(
3887:E
3844:n
3821:.
3816:n
3810:2
3797:2
3790:]
3787:n
3784:)
3778:+
3775:p
3772:(
3766:)
3763:)
3760:m
3757:(
3754:E
3751:,
3748:y
3745:(
3739:[
3732:p
3719:e
3715:r
3711:P
3680:)
3677:)
3674:m
3671:(
3668:E
3665:,
3662:y
3659:(
3650:)
3647:)
3640:m
3636:(
3633:E
3630:,
3627:y
3624:(
3599:k
3595:}
3591:1
3588:,
3585:0
3582:{
3572:m
3548:)
3545:m
3542:(
3539:E
3519:n
3516:)
3510:+
3507:p
3504:(
3484:y
3461:m
3441:)
3438:y
3435:(
3432:D
3412:y
3389:.
3385:]
3381:]
3378:m
3372:)
3369:e
3366:+
3363:)
3360:m
3357:(
3354:E
3351:(
3348:D
3345:[
3338:p
3325:e
3316:[
3310:E
3305:E
3281:m
3251:k
3247:}
3243:1
3240:,
3237:0
3234:{
3228:m
3188:p
3151:m
3131:m
3121:n
3105:p
3078:E
3056:k
3052:}
3048:1
3045:,
3042:0
3039:{
3033:m
2993:p
2973:)
2970:D
2967:,
2964:E
2961:(
2934:D
2914:)
2911:)
2908:m
2905:(
2902:E
2899:,
2896:y
2893:(
2865:k
2861:}
2857:1
2854:,
2851:0
2848:{
2842:m
2820:n
2816:}
2812:1
2809:,
2806:0
2803:{
2797:y
2775:k
2771:}
2767:1
2764:,
2761:0
2758:{
2750:n
2746:}
2742:1
2739:,
2736:0
2733:{
2730::
2727:D
2707:E
2685:n
2681:}
2677:1
2674:,
2671:0
2668:{
2662:)
2659:m
2656:(
2653:E
2631:k
2627:}
2623:1
2620:,
2617:0
2614:{
2608:m
2586:n
2582:}
2578:1
2575:,
2572:0
2569:{
2561:k
2557:}
2553:1
2550:,
2547:0
2544:{
2541::
2538:E
2506:k
2484:p
2457:E
2435:k
2431:}
2427:1
2424:,
2421:0
2418:{
2403:.
2389:n
2377:2
2370:]
2367:m
2361:)
2358:e
2355:+
2352:)
2349:m
2346:(
2343:E
2340:(
2337:D
2334:[
2327:p
2314:e
2282:k
2278:}
2274:1
2271:,
2268:0
2265:{
2259:m
2237:k
2233:}
2229:1
2226:,
2223:0
2220:{
2212:n
2208:}
2204:1
2201:,
2198:0
2195:{
2192::
2189:D
2167:n
2163:}
2159:1
2156:,
2153:0
2150:{
2142:k
2138:}
2134:1
2131:,
2128:0
2125:{
2122::
2119:E
2096:n
2093:)
2090:)
2084:+
2081:p
2078:(
2075:H
2069:1
2066:(
2057:k
2017:p
1997:n
1977:p
1968:2
1965:1
1950:0
1930:,
1924:2
1921:1
1912:p
1880:p
1867:e
1847:p
1841:1
1821:0
1801:p
1781:1
1755:p
1728:e
1703:p
1658:)
1655:p
1652:(
1644:b
1640:H
1633:1
1630:=
1621:C
1600:)
1597:x
1594:(
1589:X
1585:p
1564:)
1561:Y
1558:(
1555:H
1535:Y
1515:)
1512:x
1509:(
1504:X
1500:p
1479:)
1476:Y
1473:(
1470:H
1447:)
1444:x
1441:=
1438:X
1434:|
1430:Y
1427:(
1424:H
1393:,
1390:)
1387:p
1384:(
1376:b
1372:H
1365:)
1362:Y
1359:(
1356:H
1353:=
1343:)
1340:p
1337:(
1329:b
1325:H
1320:)
1317:x
1314:(
1309:X
1305:p
1298:}
1295:1
1292:,
1289:0
1286:{
1280:x
1269:)
1266:Y
1263:(
1260:H
1257:=
1246:)
1243:x
1240:=
1237:X
1233:|
1229:Y
1226:(
1223:H
1220:)
1217:x
1214:(
1209:X
1205:p
1198:}
1195:1
1192:,
1189:0
1186:{
1180:x
1169:)
1166:Y
1163:(
1160:H
1157:=
1147:)
1144:X
1140:|
1136:Y
1133:(
1130:H
1124:)
1121:Y
1118:(
1115:H
1112:=
1105:)
1102:Y
1099:;
1096:X
1093:(
1090:I
1059:}
1054:)
1051:Y
1048:;
1045:X
1042:(
1039:I
1034:{
1028:)
1025:x
1022:(
1017:X
1013:p
1004:=
1001:C
979:)
976:x
973:(
968:X
964:p
923:x
917:1
913:1
903:2
895:)
892:x
886:1
883:(
880:+
875:x
872:1
862:2
854:x
851:=
848:)
845:x
842:(
834:b
830:H
802:)
799:p
796:(
788:b
784:H
760:,
757:)
754:p
751:(
743:b
739:H
732:1
729:=
720:C
691:x
687:y
661:2
657:/
653:1
647:p
641:1
621:2
617:/
613:1
607:p
587:2
583:/
579:1
573:p
567:0
540:p
534:1
531:=
524:]
521:1
518:=
515:X
511:|
507:1
504:=
501:Y
498:[
485:p
482:=
475:]
472:0
469:=
466:X
462:|
458:1
455:=
452:Y
449:[
436:p
433:=
426:]
423:1
420:=
417:X
413:|
409:0
406:=
403:Y
400:[
387:p
381:1
378:=
371:]
368:0
365:=
362:X
358:|
354:0
351:=
348:Y
345:[
308:Y
284:X
264:p
254:p
240:p
226:p
222:p
190:b
186:H
165:)
162:p
159:(
151:b
147:H
140:1
126:p
111:p
86:p
69:)
63:(
58:)
54:(
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
.svg)
