2701:
246:, which quantifies the minimal description length of an object, is more suitable to describe the limits of data compression. Shannon entropy takes into account only frequency regularities while Kolmogorov complexity takes into account all algorithmic regularities, so in general the latter is smaller. On the other hand, if an object is generated by a random process in such a way that it has only frequency regularities, entropy is close to complexity with high probability (Shen et al. 2017).
2208:
42:
3354:
2696:{\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}}
3564:
1204:
223:
data tends to infinity, it is impossible to compress such data such that the code rate (average number of bits per symbol) is less than the
Shannon entropy of the source, without it being virtually certain that information will be lost. However it is possible to get the code rate arbitrarily close to
3100:
363:
coded sequence represents the compressed message in a biunivocal way, under the assumption that the decoder knows the source. From a practical point of view, this hypothesis is not always true. Consequently, when the entropy encoding is applied the transmitted message is
1502:
3391:
2024:
1832:
690:
261:
to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding). This is one approach to
1022:
3349:{\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}
1673:
1327:
2029:
The encoding algorithm: the encoder checks if the input sequence lies within the typical set; if yes, it outputs the index of the input sequence within the typical set; if not, the encoder outputs an arbitrary
2961:
3664:
3888:
3105:
2864:
2213:
2785:
991:
3085:
1897:
1738:
1571:
281:
3017:
1368:
2179:
433:
734:
220:
201:
1353:
3559:{\displaystyle A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}.}
715:
1922:
3770:
1745:
361:
580:
1199:{\displaystyle A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}.}
164:
1601:
3790:
3601:. Now we just encode the sequences in the typical set, and usual methods in source coding show that the cardinality of this set is smaller than
3883:
1240:
96:
274:
In information theory, the source coding theorem (Shannon 1948) informally states that (MacKay 2003, pg. 81, Cover 2006, Chapter 5):
3846:
3823:
3754:
2875:
1356:
1210:
107:
157:
3604:
81:
3799:
2807:
3723:
757:
232:
133:
51:
2720:
867:
138:
3868:
3028:
150:
112:
435:. Usually, the information that characterizes the source is inserted at the beginning of the transmitted message.
3878:
1837:
1678:
177:
This article is about the theory of source coding in data compression. For the term in computer programming, see
1514:
1497:{\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}}
231:
places an upper and a lower bound on the minimal possible expected length of codewords as a function of the
3873:
2972:
3090:
and so by Kraft's inequality there exists a prefix-free code having those word lengths. Thus the minimal
242:
Note that, for data that exhibits more dependencies (whose source is not an i.i.d. random variable), the
2126:
2056:), the encoder does not make any error. So, the probability of error of the encoder is bounded above by
367:
243:
3743:
Shen, A. and
Uspensky, V.A. and Vereshchagin, N. (2017). "Chapter 7.3. : Complexity and entropy".
2711:
2707:
771:
505:
76:
56:
1332:
3787:
2049:
digit number. As long as the input sequence lies within the typical set (with probability at least
2019:{\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n(H(X)+\varepsilon )}
61:
698:
3764:
1362:
The definition of typical sets implies that those sequences that lie in the typical set satisfy:
782:
258:
185:
71:
33:
3842:
3819:
3750:
1827:{\displaystyle \left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}}
3814:
263:
197:
128:
86:
685:{\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} <{\frac {H(X)}{\log _{2}a}}+1}
334:
3794:
236:
205:
3718:
3713:
718:
212:
3365:
Fixed rate lossless source coding for discrete time non-stationary independent sources
3862:
66:
17:
41:
3783:
1217:, the probability that a sequence generated by the source lies in the typical set,
91:
3836:
3744:
997:
738:
479:
178:
2082:(in the sense of exponent) would cover a set of probability bounded away from
1668:{\displaystyle \left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}}
774:
in the continuous-valued case. The Source coding theorem states that for any
570:
is optimal in the sense that it has the minimal expected word length for
799:
2066:: the converse is proved by showing that any set of size smaller than
1322:{\displaystyle P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })}
1329:
can be made arbitrarily close to 1, and specifically, greater than
1233:, as defined approaches one. In particular, for sufficiently large
841:
are recoverable from the binary bits with probability of at least
221:
independent and identically-distributed random variable (i.i.d.)
2956:{\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}
1899:
and the lower bound on the total probability of the whole set
306:
257:
is a mapping from (a sequence of) symbols from an information
547:
denote the random variable given by the length of codeword
327:
bits it is virtually certain that information will be lost.
3659:{\displaystyle 2^{n({\overline {H_{n}}}(X)+\varepsilon )}}
1675:, which follows from the left hand side (lower bound) for
224:
the
Shannon entropy, with negligible probability of loss.
3803:, vol. 27, pp. 379–423, 623-656, July, October, 1948
316:; but conversely, if they are compressed into fewer than
3835:
Cover, Thomas M. (2006). "Chapter 5: Data
Compression".
3685:
bits suffice for encoding with probability greater than
219:
shows that, in the limit, as the length of a stream of
3815:
Information Theory, Inference, and
Learning Algorithms
3889:
Mathematical theorems in theoretical computer science
3607:
3394:
3103:
3031:
2975:
2878:
2810:
2723:
2211:
2129:
1925:
1840:
1748:
1681:
1604:
1517:
1371:
1335:
1243:
1025:
870:
701:
583:
370:
337:
2026:
bits are enough to point to any string in this set.
2859:{\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }
202:
independent identically-distributed random variable
27:
Establishes the limits to possible data compression
3658:
3558:
3348:
3079:
3011:
2955:
2858:
2779:
2695:
2173:
2018:
1891:
1826:
1732:
1667:
1565:
1496:
1347:
1321:
1198:
985:
709:
684:
427:
355:
2780:{\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}
986:{\displaystyle p(x_{1},\ldots ,x_{n})=\Pr \left.}
196:) establishes the statistical limits to possible
3746:Kolmogorov Complexity and Algorithmic Randomness
3080:{\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1}
912:
3360:Extension to non-stationary independent sources
3749:. American Mathematical Society. p. 226.
3818:Cambridge: Cambridge University Press, 2003.
2090:Proof: Source coding theorem for symbol codes
309:with negligible risk of information loss, as
158:
8:
3769:: CS1 maint: multiple names: authors list (
2853:
2824:
3841:. John Wiley & Sons. pp. 103–142.
1892:{\displaystyle p(x_{1},x_{2},\cdots x_{n})}
1733:{\displaystyle p(x_{1},x_{2},\cdots x_{n})}
1566:{\displaystyle (X_{1},X_{2},\cdots X_{n})}
239:) and of the size of the target alphabet.
165:
151:
29:
3700:can be made arbitrarily small, by making
3625:
3619:
3612:
3606:
3517:
3511:
3497:
3478:
3450:
3427:
3422:
3404:
3399:
3393:
3321:
3300:
3269:
3257:
3244:
3237:
3231:
3194:
3181:
3163:
3140:
3130:
3109:
3108:
3104:
3102:
3065:
3047:
3039:
3030:
3003:
2988:
2980:
2974:
2941:
2928:
2912:
2899:
2886:
2877:
2847:
2834:
2815:
2809:
2763:
2755:
2745:
2734:
2722:
2677:
2666:
2665:
2643:
2633:
2623:
2610:
2599:
2570:
2555:
2547:
2534:
2524:
2514:
2503:
2474:
2464:
2454:
2443:
2428:
2420:
2407:
2397:
2387:
2376:
2353:
2340:
2330:
2320:
2309:
2286:
2273:
2263:
2253:
2242:
2212:
2210:
2163:
2155:
2147:
2134:
2128:
1956:
1939:
1934:
1924:
1880:
1864:
1851:
1839:
1794:
1762:
1757:
1747:
1721:
1705:
1692:
1680:
1635:
1618:
1613:
1603:
1554:
1538:
1525:
1516:
1461:
1443:
1424:
1376:
1370:
1334:
1310:
1305:
1289:
1270:
1257:
1242:
1162:
1146:
1127:
1101:
1075:
1056:
1035:
1030:
1024:
969:
956:
937:
924:
900:
881:
869:
835:binary bits such that the source symbols
703:
702:
700:
661:
640:
624:
623:
605:
584:
582:
369:
336:
2114:denote the word length of each possible
235:of the input word (which is viewed as a
3735:
32:
3788:A Mathematical Theory of Communication
3762:
489:is a random variable taking values in
439:Source coding theorem for symbol codes
229:source coding theorem for symbol codes
2801:For the second inequality we may set
1834:, which follows from upper bound for
802:of the source, there is large enough
482:from those alphabets (respectively).
204:, and the operational meaning of the
7:
3012:{\displaystyle a^{-s_{i}}\leq p_{i}}
454:denote two finite alphabets and let
2706:where the second line follows from
284:random variables each with entropy
97:Limiting density of discrete points
2174:{\displaystyle q_{i}=a^{-s_{i}}/C}
1213:(AEP) shows that for large enough
428:{\displaystyle NH(X)+(inf.source)}
25:
1211:asymptotic equipartition property
810:i.i.d. repetition of the source,
295:can be compressed into more than
108:Asymptotic equipartition property
2710:and the fifth line follows from
770:in the discrete-valued case and
40:
190:Shannon's source coding theorem
124:Shannon's source coding theorem
3838:Elements of Information Theory
3651:
3642:
3636:
3616:
3534:
3528:
3312:
3306:
2225:
2219:
2013:
2004:
1998:
1992:
1981:
1972:
1966:
1960:
1886:
1844:
1819:
1810:
1804:
1798:
1787:
1775:
1727:
1685:
1660:
1651:
1645:
1639:
1560:
1518:
1511:The probability of a sequence
1489:
1480:
1474:
1468:
1404:
1395:
1389:
1383:
1348:{\displaystyle 1-\varepsilon }
1316:
1295:
1250:
1247:
1174:
1168:
1152:
1120:
1081:
1049:
906:
874:
652:
646:
634:
628:
596:
590:
422:
389:
383:
377:
350:
344:
82:Conditional mutual information
1:
3800:Bell System Technical Journal
3884:Presentation layer protocols
3724:Noisy-channel coding theorem
3631:
3523:
725:Proof: source coding theorem
710:{\displaystyle \mathbb {E} }
200:for data whose source is an
134:Noisy-channel coding theorem
3905:
806:and an encoder that takes
176:
1016:, is defined as follows:
194:noiseless coding theorem
3666:. Thus, on an average,
852:Proof of Achievability.
574:, then (Shannon 1948):
480:set of all finite words
139:Shannon–Hartley theorem
3660:
3560:
3350:
3081:
3013:
2957:
2860:
2781:
2750:
2697:
2615:
2519:
2459:
2392:
2325:
2258:
2175:
2020:
1893:
1828:
1734:
1669:
1567:
1498:
1349:
1323:
1200:
987:
711:
686:
429:
357:
329:
113:Rate–distortion theory
3661:
3561:
3351:
3082:
3014:
2958:
2861:
2782:
2730:
2698:
2595:
2499:
2439:
2372:
2305:
2238:
2176:
2021:
1894:
1829:
1735:
1670:
1568:
1499:
1350:
1324:
1201:
988:
712:
687:
430:
358:
356:{\displaystyle NH(X)}
276:
270:Source coding theorem
244:Kolmogorov complexity
217:source coding theorem
18:Source coding theorem
3812:David J. C. MacKay.
3605:
3392:
3101:
3029:
2973:
2876:
2808:
2721:
2209:
2127:
1923:
1838:
1746:
1679:
1602:
1515:
1369:
1333:
1241:
1023:
868:
772:differential entropy
699:
581:
368:
335:
77:Directed information
57:Differential entropy
3432:
3409:
3369:Define typical set
1944:
1767:
1623:
1315:
1040:
62:Conditional entropy
3869:Information theory
3793:2009-02-16 at the
3656:
3556:
3418:
3395:
3346:
3344:
3077:
3009:
2953:
2856:
2777:
2712:Kraft's inequality
2693:
2691:
2185:is chosen so that
2171:
2016:
1930:
1889:
1824:
1753:
1730:
1665:
1609:
1563:
1494:
1345:
1319:
1301:
1196:
1026:
983:
707:
682:
506:uniquely decodable
425:
353:
186:information theory
72:Mutual information
34:Information theory
3634:
3526:
3458:
3441:
3435:
3334:
3282:
2708:Gibbs' inequality
2064:Proof of converse
1573:being drawn from
1109:
1092:
1086:
816:, and maps it to
674:
618:
175:
174:
16:(Redirected from
3896:
3879:Data compression
3853:
3852:
3832:
3826:
3810:
3804:
3781:
3775:
3774:
3768:
3760:
3740:
3703:
3699:
3695:
3691:
3684:
3675:
3665:
3663:
3662:
3657:
3655:
3654:
3635:
3630:
3629:
3620:
3600:
3595:
3594:
3579:
3575:
3569:Then, for given
3565:
3563:
3562:
3557:
3552:
3548:
3541:
3537:
3527:
3522:
3521:
3512:
3507:
3503:
3502:
3501:
3483:
3482:
3459:
3451:
3439:
3433:
3431:
3426:
3408:
3403:
3384:
3383:
3382:
3355:
3353:
3352:
3347:
3345:
3335:
3333:
3326:
3325:
3315:
3301:
3293:
3283:
3281:
3274:
3273:
3263:
3262:
3261:
3249:
3248:
3238:
3236:
3235:
3214:
3210:
3206:
3199:
3198:
3186:
3185:
3168:
3167:
3149:
3145:
3144:
3135:
3134:
3112:
3093:
3086:
3084:
3083:
3078:
3070:
3069:
3054:
3053:
3052:
3051:
3018:
3016:
3015:
3010:
3008:
3007:
2995:
2994:
2993:
2992:
2962:
2960:
2959:
2954:
2946:
2945:
2933:
2932:
2917:
2916:
2904:
2903:
2891:
2890:
2865:
2863:
2862:
2857:
2852:
2851:
2839:
2838:
2820:
2819:
2797:
2786:
2784:
2783:
2778:
2770:
2769:
2768:
2767:
2749:
2744:
2702:
2700:
2699:
2694:
2692:
2682:
2681:
2669:
2658:
2648:
2647:
2638:
2637:
2628:
2627:
2614:
2609:
2585:
2575:
2574:
2562:
2561:
2560:
2559:
2539:
2538:
2529:
2528:
2518:
2513:
2489:
2479:
2478:
2469:
2468:
2458:
2453:
2435:
2434:
2433:
2432:
2412:
2411:
2402:
2401:
2391:
2386:
2362:
2358:
2357:
2345:
2344:
2335:
2334:
2324:
2319:
2295:
2291:
2290:
2278:
2277:
2268:
2267:
2257:
2252:
2201:
2184:
2180:
2178:
2177:
2172:
2167:
2162:
2161:
2160:
2159:
2139:
2138:
2122:
2113:
2104:
2085:
2081:
2080:
2079:
2059:
2055:
2048:
2025:
2023:
2022:
2017:
1985:
1984:
1948:
1943:
1938:
1914:
1913:
1912:
1898:
1896:
1895:
1890:
1885:
1884:
1869:
1868:
1856:
1855:
1833:
1831:
1830:
1825:
1823:
1822:
1771:
1766:
1761:
1739:
1737:
1736:
1731:
1726:
1725:
1710:
1709:
1697:
1696:
1674:
1672:
1671:
1666:
1664:
1663:
1627:
1622:
1617:
1595:
1589:is greater than
1588:
1587:
1586:
1572:
1570:
1569:
1564:
1559:
1558:
1543:
1542:
1530:
1529:
1503:
1501:
1500:
1495:
1493:
1492:
1453:
1449:
1448:
1447:
1429:
1428:
1408:
1407:
1354:
1352:
1351:
1346:
1328:
1326:
1325:
1320:
1314:
1309:
1294:
1293:
1275:
1274:
1262:
1261:
1236:
1232:
1231:
1230:
1216:
1205:
1203:
1202:
1197:
1192:
1188:
1181:
1177:
1167:
1166:
1151:
1150:
1132:
1131:
1110:
1102:
1090:
1084:
1080:
1079:
1061:
1060:
1039:
1034:
1015:
1014:
1013:
992:
990:
989:
984:
979:
975:
974:
973:
961:
960:
942:
941:
929:
928:
905:
904:
886:
885:
860:
847:
840:
834:
815:
809:
805:
798:larger than the
797:
780:
769:
755:
732:
716:
714:
713:
708:
706:
691:
689:
688:
683:
675:
673:
666:
665:
655:
641:
627:
619:
617:
610:
609:
599:
585:
573:
569:
558:
546:
542:
531:
530:
529:
519:
518:
517:
503:
495:
488:
477:
476:
475:
465:
464:
463:
453:
434:
432:
431:
426:
362:
360:
359:
354:
326:
315:
305:
294:
280:
264:data compression
198:data compression
167:
160:
153:
129:Channel capacity
87:Relative entropy
44:
30:
21:
3904:
3903:
3899:
3898:
3897:
3895:
3894:
3893:
3859:
3858:
3857:
3856:
3849:
3834:
3833:
3829:
3811:
3807:
3795:Wayback Machine
3782:
3778:
3761:
3757:
3742:
3741:
3737:
3732:
3710:
3701:
3697:
3693:
3686:
3673:
3668:
3667:
3621:
3608:
3603:
3602:
3593:
3588:
3587:
3586:
3581:
3577:
3570:
3513:
3493:
3474:
3473:
3469:
3446:
3442:
3417:
3413:
3390:
3389:
3381:
3376:
3375:
3374:
3370:
3367:
3362:
3343:
3342:
3317:
3316:
3302:
3291:
3290:
3265:
3264:
3253:
3240:
3239:
3227:
3212:
3211:
3190:
3177:
3173:
3169:
3159:
3147:
3146:
3136:
3126:
3116:
3099:
3098:
3091:
3061:
3043:
3035:
3027:
3026:
2999:
2984:
2976:
2971:
2970:
2937:
2924:
2908:
2895:
2882:
2874:
2873:
2843:
2830:
2811:
2806:
2805:
2791:
2759:
2751:
2719:
2718:
2690:
2689:
2673:
2656:
2655:
2639:
2629:
2619:
2583:
2582:
2566:
2551:
2543:
2530:
2520:
2487:
2486:
2470:
2460:
2424:
2416:
2403:
2393:
2360:
2359:
2349:
2336:
2326:
2293:
2292:
2282:
2269:
2259:
2228:
2207:
2206:
2198:
2192:
2186:
2182:
2151:
2143:
2130:
2125:
2124:
2120:
2115:
2111:
2106:
2095:
2092:
2083:
2078:
2073:
2072:
2071:
2067:
2057:
2050:
2031:
1952:
1926:
1921:
1920:
1911:
1906:
1905:
1904:
1900:
1876:
1860:
1847:
1836:
1835:
1790:
1749:
1744:
1743:
1717:
1701:
1688:
1677:
1676:
1631:
1605:
1600:
1599:
1590:
1585:
1580:
1579:
1578:
1574:
1550:
1534:
1521:
1513:
1512:
1507:
1457:
1439:
1420:
1419:
1415:
1372:
1367:
1366:
1331:
1330:
1285:
1266:
1253:
1239:
1238:
1234:
1229:
1224:
1223:
1222:
1218:
1214:
1158:
1142:
1123:
1097:
1093:
1071:
1052:
1048:
1044:
1021:
1020:
1012:
1007:
1006:
1005:
1001:
965:
952:
933:
920:
919:
915:
896:
877:
866:
865:
855:
842:
836:
817:
811:
807:
803:
785:
781:, i.e. for any
775:
760:
756:is i.i.d. with
753:
747:
741:
730:
727:
697:
696:
657:
656:
642:
601:
600:
586:
579:
578:
571:
563:
548:
544:
537:
533:
528:
525:
524:
523:
521:
516:
513:
512:
511:
509:
497:
494:
490:
486:
474:
471:
470:
469:
467:
462:
459:
458:
457:
455:
452:
448:
444:
441:
366:
365:
333:
332:
317:
310:
296:
285:
278:
272:
252:
237:random variable
206:Shannon entropy
182:
171:
28:
23:
22:
15:
12:
11:
5:
3902:
3900:
3892:
3891:
3886:
3881:
3876:
3871:
3861:
3860:
3855:
3854:
3847:
3827:
3805:
3776:
3755:
3734:
3733:
3731:
3728:
3727:
3726:
3721:
3719:Error exponent
3716:
3714:Channel coding
3709:
3706:
3671:
3653:
3650:
3647:
3644:
3641:
3638:
3633:
3628:
3624:
3618:
3615:
3611:
3589:
3580:large enough,
3567:
3566:
3555:
3551:
3547:
3544:
3540:
3536:
3533:
3530:
3525:
3520:
3516:
3510:
3506:
3500:
3496:
3492:
3489:
3486:
3481:
3477:
3472:
3468:
3465:
3462:
3457:
3454:
3449:
3445:
3438:
3430:
3425:
3421:
3416:
3412:
3407:
3402:
3398:
3377:
3366:
3363:
3361:
3358:
3357:
3356:
3341:
3338:
3332:
3329:
3324:
3320:
3314:
3311:
3308:
3305:
3299:
3296:
3294:
3292:
3289:
3286:
3280:
3277:
3272:
3268:
3260:
3256:
3252:
3247:
3243:
3234:
3230:
3226:
3223:
3220:
3217:
3215:
3213:
3209:
3205:
3202:
3197:
3193:
3189:
3184:
3180:
3176:
3172:
3166:
3162:
3158:
3155:
3152:
3150:
3148:
3143:
3139:
3133:
3129:
3125:
3122:
3119:
3117:
3115:
3111:
3107:
3106:
3088:
3087:
3076:
3073:
3068:
3064:
3060:
3057:
3050:
3046:
3042:
3038:
3034:
3020:
3019:
3006:
3002:
2998:
2991:
2987:
2983:
2979:
2964:
2963:
2952:
2949:
2944:
2940:
2936:
2931:
2927:
2923:
2920:
2915:
2911:
2907:
2902:
2898:
2894:
2889:
2885:
2881:
2867:
2866:
2855:
2850:
2846:
2842:
2837:
2833:
2829:
2826:
2823:
2818:
2814:
2788:
2787:
2776:
2773:
2766:
2762:
2758:
2754:
2748:
2743:
2740:
2737:
2733:
2729:
2726:
2704:
2703:
2688:
2685:
2680:
2676:
2672:
2668:
2664:
2661:
2659:
2657:
2654:
2651:
2646:
2642:
2636:
2632:
2626:
2622:
2618:
2613:
2608:
2605:
2602:
2598:
2594:
2591:
2588:
2586:
2584:
2581:
2578:
2573:
2569:
2565:
2558:
2554:
2550:
2546:
2542:
2537:
2533:
2527:
2523:
2517:
2512:
2509:
2506:
2502:
2498:
2495:
2492:
2490:
2488:
2485:
2482:
2477:
2473:
2467:
2463:
2457:
2452:
2449:
2446:
2442:
2438:
2431:
2427:
2423:
2419:
2415:
2410:
2406:
2400:
2396:
2390:
2385:
2382:
2379:
2375:
2371:
2368:
2365:
2363:
2361:
2356:
2352:
2348:
2343:
2339:
2333:
2329:
2323:
2318:
2315:
2312:
2308:
2304:
2301:
2298:
2296:
2294:
2289:
2285:
2281:
2276:
2272:
2266:
2262:
2256:
2251:
2248:
2245:
2241:
2237:
2234:
2231:
2229:
2227:
2224:
2221:
2218:
2215:
2214:
2196:
2190:
2170:
2166:
2158:
2154:
2150:
2146:
2142:
2137:
2133:
2118:
2109:
2091:
2088:
2074:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1955:
1951:
1947:
1942:
1937:
1933:
1929:
1917:
1916:
1907:
1888:
1883:
1879:
1875:
1872:
1867:
1863:
1859:
1854:
1850:
1846:
1843:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1800:
1797:
1793:
1789:
1786:
1783:
1780:
1777:
1774:
1770:
1765:
1760:
1756:
1752:
1741:
1729:
1724:
1720:
1716:
1713:
1708:
1704:
1700:
1695:
1691:
1687:
1684:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1634:
1630:
1626:
1621:
1616:
1612:
1608:
1597:
1581:
1562:
1557:
1553:
1549:
1546:
1541:
1537:
1533:
1528:
1524:
1520:
1505:
1504:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1460:
1456:
1452:
1446:
1442:
1438:
1435:
1432:
1427:
1423:
1418:
1414:
1411:
1406:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1379:
1375:
1359:for a proof).
1344:
1341:
1338:
1318:
1313:
1308:
1304:
1300:
1297:
1292:
1288:
1284:
1281:
1278:
1273:
1269:
1265:
1260:
1256:
1252:
1249:
1246:
1225:
1207:
1206:
1195:
1191:
1187:
1184:
1180:
1176:
1173:
1170:
1165:
1161:
1157:
1154:
1149:
1145:
1141:
1138:
1135:
1130:
1126:
1122:
1119:
1116:
1113:
1108:
1105:
1100:
1096:
1089:
1083:
1078:
1074:
1070:
1067:
1064:
1059:
1055:
1051:
1047:
1043:
1038:
1033:
1029:
1008:
994:
993:
982:
978:
972:
968:
964:
959:
955:
951:
948:
945:
940:
936:
932:
927:
923:
918:
914:
911:
908:
903:
899:
895:
892:
889:
884:
880:
876:
873:
751:
745:
726:
723:
719:expected value
705:
693:
692:
681:
678:
672:
669:
664:
660:
654:
651:
648:
645:
639:
636:
633:
630:
626:
622:
616:
613:
608:
604:
598:
595:
592:
589:
535:
526:
514:
492:
472:
460:
450:
446:
440:
437:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
352:
349:
346:
343:
340:
271:
268:
251:
248:
213:Claude Shannon
173:
172:
170:
169:
162:
155:
147:
144:
143:
142:
141:
136:
131:
126:
118:
117:
116:
115:
110:
102:
101:
100:
99:
94:
89:
84:
79:
74:
69:
64:
59:
54:
46:
45:
37:
36:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3901:
3890:
3887:
3885:
3882:
3880:
3877:
3875:
3874:Coding theory
3872:
3870:
3867:
3866:
3864:
3850:
3848:0-471-24195-4
3844:
3840:
3839:
3831:
3828:
3825:
3824:0-521-64298-1
3821:
3817:
3816:
3809:
3806:
3802:
3801:
3796:
3792:
3789:
3785:
3780:
3777:
3772:
3766:
3758:
3756:9781470431822
3752:
3748:
3747:
3739:
3736:
3729:
3725:
3722:
3720:
3717:
3715:
3712:
3711:
3707:
3705:
3690:
3683:
3679:
3674:
3648:
3645:
3639:
3626:
3622:
3613:
3609:
3599:
3592:
3585:
3573:
3553:
3549:
3545:
3542:
3538:
3531:
3518:
3514:
3508:
3504:
3498:
3494:
3490:
3487:
3484:
3479:
3475:
3470:
3466:
3463:
3460:
3455:
3452:
3447:
3443:
3436:
3428:
3423:
3419:
3414:
3410:
3405:
3400:
3396:
3388:
3387:
3386:
3380:
3373:
3364:
3359:
3339:
3336:
3330:
3327:
3322:
3318:
3309:
3303:
3297:
3295:
3287:
3284:
3278:
3275:
3270:
3266:
3258:
3254:
3250:
3245:
3241:
3232:
3228:
3224:
3221:
3218:
3216:
3207:
3203:
3200:
3195:
3191:
3187:
3182:
3178:
3174:
3170:
3164:
3160:
3156:
3153:
3151:
3141:
3137:
3131:
3127:
3123:
3120:
3118:
3113:
3097:
3096:
3095:
3074:
3071:
3066:
3062:
3058:
3055:
3048:
3044:
3040:
3036:
3032:
3025:
3024:
3023:
3004:
3000:
2996:
2989:
2985:
2981:
2977:
2969:
2968:
2967:
2950:
2947:
2942:
2938:
2934:
2929:
2925:
2921:
2918:
2913:
2909:
2905:
2900:
2896:
2892:
2887:
2883:
2879:
2872:
2871:
2870:
2848:
2844:
2840:
2835:
2831:
2827:
2821:
2816:
2812:
2804:
2803:
2802:
2799:
2795:
2774:
2771:
2764:
2760:
2756:
2752:
2746:
2741:
2738:
2735:
2731:
2727:
2724:
2717:
2716:
2715:
2713:
2709:
2686:
2683:
2678:
2674:
2670:
2662:
2660:
2652:
2649:
2644:
2640:
2634:
2630:
2624:
2620:
2616:
2611:
2606:
2603:
2600:
2596:
2592:
2589:
2587:
2579:
2576:
2571:
2567:
2563:
2556:
2552:
2548:
2544:
2540:
2535:
2531:
2525:
2521:
2515:
2510:
2507:
2504:
2500:
2496:
2493:
2491:
2483:
2480:
2475:
2471:
2465:
2461:
2455:
2450:
2447:
2444:
2440:
2436:
2429:
2425:
2421:
2417:
2413:
2408:
2404:
2398:
2394:
2388:
2383:
2380:
2377:
2373:
2369:
2366:
2364:
2354:
2350:
2346:
2341:
2337:
2331:
2327:
2321:
2316:
2313:
2310:
2306:
2302:
2299:
2297:
2287:
2283:
2279:
2274:
2270:
2264:
2260:
2254:
2249:
2246:
2243:
2239:
2235:
2232:
2230:
2222:
2216:
2205:
2204:
2203:
2199:
2189:
2168:
2164:
2156:
2152:
2148:
2144:
2140:
2135:
2131:
2121:
2112:
2103:
2099:
2089:
2087:
2077:
2070:
2065:
2061:
2054:
2046:
2042:
2038:
2034:
2027:
2010:
2007:
2001:
1995:
1989:
1986:
1978:
1975:
1969:
1963:
1957:
1953:
1949:
1945:
1940:
1935:
1931:
1927:
1910:
1903:
1881:
1877:
1873:
1870:
1865:
1861:
1857:
1852:
1848:
1841:
1816:
1813:
1807:
1801:
1795:
1791:
1784:
1781:
1778:
1772:
1768:
1763:
1758:
1754:
1750:
1742:
1722:
1718:
1714:
1711:
1706:
1702:
1698:
1693:
1689:
1682:
1657:
1654:
1648:
1642:
1636:
1632:
1628:
1624:
1619:
1614:
1610:
1606:
1598:
1594:
1584:
1577:
1555:
1551:
1547:
1544:
1539:
1535:
1531:
1526:
1522:
1510:
1509:
1508:
1486:
1483:
1477:
1471:
1465:
1462:
1458:
1454:
1450:
1444:
1440:
1436:
1433:
1430:
1425:
1421:
1416:
1412:
1409:
1401:
1398:
1392:
1386:
1380:
1377:
1373:
1365:
1364:
1363:
1360:
1358:
1342:
1339:
1336:
1311:
1306:
1302:
1298:
1290:
1286:
1282:
1279:
1276:
1271:
1267:
1263:
1258:
1254:
1244:
1228:
1221:
1212:
1193:
1189:
1185:
1182:
1178:
1171:
1163:
1159:
1155:
1147:
1143:
1139:
1136:
1133:
1128:
1124:
1117:
1114:
1111:
1106:
1103:
1098:
1094:
1087:
1076:
1072:
1068:
1065:
1062:
1057:
1053:
1045:
1041:
1036:
1031:
1027:
1019:
1018:
1017:
1011:
1004:
999:
980:
976:
970:
966:
962:
957:
953:
949:
946:
943:
938:
934:
930:
925:
921:
916:
909:
901:
897:
893:
890:
887:
882:
878:
871:
864:
863:
862:
858:
853:
849:
846:
839:
832:
828:
824:
820:
814:
801:
796:
792:
788:
784:
778:
773:
767:
763:
759:
754:
744:
740:
736:
724:
722:
720:
679:
676:
670:
667:
662:
658:
649:
643:
637:
631:
620:
614:
611:
606:
602:
593:
587:
577:
576:
575:
567:
560:
556:
552:
541:
507:
501:
485:Suppose that
483:
481:
438:
436:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
386:
380:
374:
371:
347:
341:
338:
328:
324:
320:
313:
308:
303:
299:
292:
288:
283:
275:
269:
267:
265:
260:
256:
255:Source coding
249:
247:
245:
240:
238:
234:
230:
225:
222:
218:
214:
209:
207:
203:
199:
195:
191:
187:
180:
168:
163:
161:
156:
154:
149:
148:
146:
145:
140:
137:
135:
132:
130:
127:
125:
122:
121:
120:
119:
114:
111:
109:
106:
105:
104:
103:
98:
95:
93:
90:
88:
85:
83:
80:
78:
75:
73:
70:
68:
67:Joint entropy
65:
63:
60:
58:
55:
53:
50:
49:
48:
47:
43:
39:
38:
35:
31:
19:
3837:
3830:
3813:
3808:
3798:
3784:C.E. Shannon
3779:
3745:
3738:
3688:
3681:
3677:
3669:
3597:
3590:
3583:
3571:
3568:
3378:
3371:
3368:
3089:
3021:
2965:
2868:
2800:
2793:
2789:
2705:
2194:
2187:
2116:
2107:
2101:
2097:
2093:
2075:
2068:
2063:
2062:
2052:
2044:
2040:
2036:
2032:
2028:
1918:
1908:
1901:
1592:
1582:
1575:
1506:
1361:
1226:
1219:
1208:
1009:
1002:
995:
856:
851:
850:
844:
837:
830:
826:
822:
818:
812:
794:
790:
786:
776:
765:
761:
749:
742:
737:source, its
728:
717:denotes the
694:
565:
561:
554:
550:
539:
499:
484:
442:
330:
322:
318:
311:
301:
297:
290:
286:
277:
273:
254:
253:
241:
228:
226:
216:
211:Named after
210:
193:
189:
183:
123:
92:Entropy rate
3596:) > 1 −
998:typical set
739:time series
478:denote the
179:Source code
3863:Categories
3730:References
3094:satisfies
861:, and let
721:operator.
508:code from
250:Statements
3765:cite book
3649:ε
3632:¯
3546:ε
3524:¯
3509:−
3488:⋯
3464:
3448:−
3406:ε
3328:
3276:
3251:
3225:−
3222:∑
3188:
3175:−
3157:∑
3124:∑
3059:∑
3056:≤
3041:−
3033:∑
2997:≤
2982:−
2935:
2922:−
2906:≤
2893:
2880:−
2854:⌉
2841:
2828:−
2825:⌈
2772:≤
2757:−
2732:∑
2684:
2650:
2617:−
2597:∑
2593:−
2590:≤
2577:
2549:−
2541:
2501:∑
2497:−
2481:
2441:∑
2422:−
2414:
2374:∑
2370:−
2347:
2307:∑
2303:−
2300:≤
2280:
2240:∑
2236:−
2149:−
2123:. Define
2011:ε
1979:ε
1950:≤
1941:ε
1874:⋯
1817:ε
1814:−
1785:ε
1782:−
1773:≥
1764:ε
1715:⋯
1658:ε
1629:≤
1620:ε
1548:⋯
1487:ε
1484:−
1463:−
1455:≤
1434:⋯
1410:≤
1402:ε
1378:−
1343:ε
1340:−
1312:ε
1299:∈
1280:⋯
1186:ε
1156:−
1137:⋯
1115:
1099:−
1066:⋯
1037:ε
947:⋯
891:…
854:Fix some
668:
621:≤
612:
319:N H
298:N H
3791:Archived
3708:See also
3704:larger.
3692:, where
2869:so that
2202:. Then
2193:+ ... +
2181:, where
553: (
496:and let
2966:and so
800:entropy
758:entropy
748:, ...,
568:
564:
549:
502:
498:
233:entropy
52:Entropy
3845:
3822:
3753:
3576:, for
3574:> 0
3440:
3434:
1919:Since
1355:(See
1091:
1085:
859:> 0
779:> 0
735:i.i.d.
733:is an
729:Given
695:Where
543:. Let
532:where
282:i.i.d.
259:source
215:, the
504:be a
3843:ISBN
3820:ISBN
3771:link
3751:ISBN
3696:and
3687:1 −
3680:) +
3543:<
3385:as:
3154:<
3022:and
2919:<
2792:log
2105:let
2096:1 ≤
2094:For
2051:1 −
2043:) +
1591:1 −
1209:The
1183:<
996:The
843:1 −
829:) +
793:) +
783:rate
638:<
538:| =
466:and
443:Let
331:The
307:bits
227:The
192:(or
3797:",
3786:, "
3582:Pr(
3461:log
3319:log
3267:log
3242:log
3179:log
2926:log
2884:log
2832:log
2796:≤ 0
2790:so
2675:log
2641:log
2568:log
2532:log
2472:log
2405:log
2338:log
2271:log
2200:= 1
1357:AEP
1112:log
659:log
603:log
562:If
520:to
449:, Σ
314:→ ∞
184:In
3865::
3767:}}
3763:{{
2798:.
2714::
2100:≤
2086:.
2060:.
1237:,
1000:,
913:Pr
848:.
559:.
534:|Σ
266:.
208:.
188:,
3851:.
3773:)
3759:.
3702:n
3698:δ
3694:ε
3689:δ
3682:ε
3678:X
3676:(
3672:n
3670:H
3652:)
3646:+
3643:)
3640:X
3637:(
3627:n
3623:H
3617:(
3614:n
3610:2
3598:δ
3591:n
3584:A
3578:n
3572:δ
3554:.
3550:}
3539:|
3535:)
3532:X
3529:(
3519:n
3515:H
3505:)
3499:n
3495:X
3491:,
3485:,
3480:1
3476:X
3471:(
3467:p
3456:n
3453:1
3444:|
3437::
3429:n
3424:1
3420:x
3415:{
3411:=
3401:n
3397:A
3379:n
3372:A
3340:1
3337:+
3331:a
3323:2
3313:)
3310:X
3307:(
3304:H
3298:=
3288:1
3285:+
3279:a
3271:2
3259:i
3255:p
3246:2
3233:i
3229:p
3219:=
3208:)
3204:1
3201:+
3196:i
3192:p
3183:a
3171:(
3165:i
3161:p
3142:i
3138:s
3132:i
3128:p
3121:=
3114:S
3110:E
3092:S
3075:1
3072:=
3067:i
3063:p
3049:i
3045:s
3037:a
3005:i
3001:p
2990:i
2986:s
2978:a
2951:1
2948:+
2943:i
2939:p
2930:a
2914:i
2910:s
2901:i
2897:p
2888:a
2849:i
2845:p
2836:a
2822:=
2817:i
2813:s
2794:C
2775:1
2765:i
2761:s
2753:a
2747:n
2742:1
2739:=
2736:i
2728:=
2725:C
2687:a
2679:2
2671:S
2667:E
2663:=
2653:a
2645:2
2635:i
2631:p
2625:i
2621:s
2612:n
2607:1
2604:=
2601:i
2580:C
2572:2
2564:+
2557:i
2553:s
2545:a
2536:2
2526:i
2522:p
2516:n
2511:1
2508:=
2505:i
2494:=
2484:C
2476:2
2466:i
2462:p
2456:n
2451:1
2448:=
2445:i
2437:+
2430:i
2426:s
2418:a
2409:2
2399:i
2395:p
2389:n
2384:1
2381:=
2378:i
2367:=
2355:i
2351:q
2342:2
2332:i
2328:p
2322:n
2317:1
2314:=
2311:i
2288:i
2284:p
2275:2
2265:i
2261:p
2255:n
2250:1
2247:=
2244:i
2233:=
2226:)
2223:X
2220:(
2217:H
2197:n
2195:q
2191:1
2188:q
2183:C
2169:C
2165:/
2157:i
2153:s
2145:a
2141:=
2136:i
2132:q
2119:i
2117:x
2110:i
2108:s
2102:n
2098:i
2084:1
2076:n
2069:A
2058:ε
2053:ε
2047:)
2045:ε
2041:X
2039:(
2037:H
2035:(
2033:n
2014:)
2008:+
2005:)
2002:X
1999:(
1996:H
1993:(
1990:n
1987:,
1982:)
1976:+
1973:)
1970:X
1967:(
1964:H
1961:(
1958:n
1954:2
1946:|
1936:n
1932:A
1928:|
1915:.
1909:n
1902:A
1887:)
1882:n
1878:x
1871:,
1866:2
1862:x
1858:,
1853:1
1849:x
1845:(
1842:p
1820:)
1811:)
1808:X
1805:(
1802:H
1799:(
1796:n
1792:2
1788:)
1779:1
1776:(
1769:|
1759:n
1755:A
1751:|
1740:.
1728:)
1723:n
1719:x
1712:,
1707:2
1703:x
1699:,
1694:1
1690:x
1686:(
1683:p
1661:)
1655:+
1652:)
1649:X
1646:(
1643:H
1640:(
1637:n
1633:2
1625:|
1615:n
1611:A
1607:|
1596:.
1593:ε
1583:n
1576:A
1561:)
1556:n
1552:X
1545:,
1540:2
1536:X
1532:,
1527:1
1523:X
1519:(
1490:)
1481:)
1478:X
1475:(
1472:H
1469:(
1466:n
1459:2
1451:)
1445:n
1441:x
1437:,
1431:,
1426:1
1422:x
1417:(
1413:p
1405:)
1399:+
1396:)
1393:X
1390:(
1387:H
1384:(
1381:n
1374:2
1337:1
1317:)
1307:n
1303:A
1296:)
1291:n
1287:X
1283:,
1277:,
1272:2
1268:X
1264:,
1259:1
1255:X
1251:(
1248:(
1245:P
1235:n
1227:n
1220:A
1215:n
1194:.
1190:}
1179:|
1175:)
1172:X
1169:(
1164:n
1160:H
1153:)
1148:n
1144:x
1140:,
1134:,
1129:1
1125:x
1121:(
1118:p
1107:n
1104:1
1095:|
1088::
1082:)
1077:n
1073:x
1069:,
1063:,
1058:1
1054:x
1050:(
1046:{
1042:=
1032:n
1028:A
1010:n
1003:A
981:.
977:]
971:n
967:x
963:=
958:n
954:X
950:,
944:,
939:1
935:x
931:=
926:1
922:X
917:[
910:=
907:)
902:n
898:x
894:,
888:,
883:1
879:x
875:(
872:p
857:ε
845:ε
838:X
833:)
831:ε
827:X
825:(
823:H
821:(
819:n
813:X
808:n
804:n
795:ε
791:X
789:(
787:H
777:ε
768:)
766:X
764:(
762:H
752:n
750:X
746:1
743:X
731:X
704:E
680:1
677:+
671:a
663:2
653:)
650:X
647:(
644:H
635:]
632:S
629:[
625:E
615:a
607:2
597:)
594:X
591:(
588:H
572:X
566:f
557:)
555:X
551:f
545:S
540:a
536:2
527:2
522:Σ
515:1
510:Σ
500:f
493:1
491:Σ
487:X
473:2
468:Σ
461:1
456:Σ
451:2
447:1
445:Σ
423:)
420:e
417:c
414:r
411:u
408:o
405:s
402:.
399:f
396:n
393:i
390:(
387:+
384:)
381:X
378:(
375:H
372:N
351:)
348:X
345:(
342:H
339:N
325:)
323:X
321:(
312:N
304:)
302:X
300:(
293:)
291:X
289:(
287:H
279:N
181:.
166:e
159:t
152:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
