У. Питерсон - Коды, исправляющие ошибки (1267328), страница 101
Текст из файла (страница 101)
В этом случае число, получаемое прибавлением С()т) к г 1т': г )У+С(У)= — Ад, делится на А и, следовательно, является кодовым числом из Айкода. Число г )т'+ С(И), рассматриваемое в записи по основанию г, содержит разряды числа С(й') в качестве младших разрядов и разряды числа о' в качестве старших разрядов. Таким образом, расстояние между двумя словами, каждое из которых состоит из числа и его проверочного символа, равно по меньшей мере минимальному расстоянию в АФ-коде. В частности, обнаружение одиночной ошибки всегда можно проводить, выбирая в качестве С(У) вычет числа — г'У по модулю г+ 1, а значения А, приведенные в табл.
15.1, можно использовать для нахождения проверочных символов кодов, исправляющих одиночные ошибки, и кодов, исправляющих одиночные ошибки и обнаруживающих двойные ошибки. Эти коды принадлежат к классу кодов, описываемых теоремой 15А. В качестве кода для числа 1 в этом случае выбирается пред- ставление в системе по основанию г вычета числа — г 1. Интересно отметить сходство этого метода кодирования и метода кодирования для циклических кодов, описанного в равд. 8.7. Замечания Арифметические коды впервые описаны в краткой статье Даймонда (63) и важной ранней работе Брауна (33).
Идея, лежащая в основе теоремы 15.1, принадлежит Рейтвейнеру 12531, а утверждение о распределении весов последовательно выбранных целых чисел сформулировано Чаном и Ридом (461. Арифметические коды с большим расстоянием, описанные в равд. 15.5, найдены независимо Берроусом (14) н Мандельбаумом 1198). Приводимое здесь короткое доказательство свойств расстояния принадлежит ТсаоВу и Ченгу 13071.
Теорема 15.8 взята из работы Питерсона 12301. Аналогичные результаты, но для логических, а не арифметических операций были получены Элайесом 170) и Питерсоном и Рабином 1237). Коды, проверочные символы которых образуют класс вычетов, предложены Гарнером (104). Представленные в табл. 15.1 коды с расстоянием, равным 3, были найдены Брауном (331, а коды с расстоянием, равным 4, построены Джоном Селфриджем, Запани 15.1. Покажите, что арифметическое расстояние является мстрикой.
15.2 (Цянь). Покажите, что если 2" (1( 2" + 2"-', то ее(1) = =1+в(! — 2 ), где через в(1) обозначен арифметический вес числа 15.3. Покажите, что если 2" + 2" — ' ( ! ( 2"+', то а(1) =- — (2я+! 1) 15.4. Докажите, что если в представлении числа Ф, 0 ( Ф ( ( г — 1, использованы слагаемые степени п + 1 или больше, то можно найти другое представление с меньшим числом слагаемых и максимальной степенью п. Приложение А. Неравенства, включающие биномиальные коэффициенты В этом приложении приводятся некоторые неравенства, полезные при оценке выражений, содержа!них биномиальные коэффициенты. Материал взят из записей, сделанных на семинаре Шеннона по теории информации в Массачусетском технологическом институте в 1956 г.
Пусть 6= 1 -ха -яй (А.1) гогда а„р~ („', + „' )1<С'„"<а (А.2) и — 1/и 6 ~«С (А.З) 2 где р = 1 — Х, а Х и р отличны от нуля. Этн два неравенства можно доказать, используя приближение Стирливга п1 = (2п)"и"'еме 'хр ( !3„з60 ° + "). (А.4) Известно (031, что если все члены ряда заменить нулями, то получится нижняя оценка для и1; если оставить только один член ряда '/мп, то получится верхняя оценка для и! н т. д.
Оценка сверху для выражения С„"=и!/(Хп)!(рп)! получается, если использовать разложение (А.4) как оценку снизу для (Ха)! и (рл) ! н взять оценку сверху для числителя, получаемую из того же самого разложения отбрасыванием всех членов ряда, начиная с ( — 1/360пэ). В результате получается а1 1 1 ~ 1 1 < „.„ехр ! — — —— 1 1 1 12на 360 !ла)~ 360 (па)~ ~ ' Это выражение симметрично относительно Х и р. Предположим, что Х =-в 1ь Тогда ! ! 1 360 (ха)з ~ 360 !пл)з 360ра и 1 1 — < —. 13л 123э ' Таким образом, ! ! ! 12ил 000 (хл)з + 200 (нлр < 12 1 1 1 + — < О. !2Хл !2нл 180!1л 1 ! 12л 12Хл Так находится верхняя граница, определяемая неравенством (А,2), Нижняя граница вычисляется аналогично на основе разложения (А.4), в котором прн оценке сверху числителя оставляется только первый член ряда, а при оценке снизу знаменателя п! отбрасываются все слагаемые ряда.
Вторая оценка снизу в неравенство (А.3) †следу нз неравен. ства (А.2), если хотя бы одно из произведений Хп и рп не меньше трех, так как в этом случае (1/12Хп) + (1/12рп) меньше чем (1/12)+(!/36) = 1/9 и ехр(-1/9) > (1/2) 1/и.
В четвертом случае, когда Хп и рп меньше трех, искомый результат получить легко. При )п = 1, рп = 1 неравенство переходит в равенство. «Хвост» биномиальиого распределения можно оценить следующим образом: (А.б) где Я = 1 — Р. Кроме того, Лл Положим, что Р = Я = !/м и умножим обе части неравенства на 2". В результате получим л С„< )' С < С„при А> — (А.7) Х С„~(А р, при 2,> —.
(А.8) Нижняя граница в неравенстве (А.б) очевидна Верхняя граница получается как оценка сверху при помощи суммы геометрической прогрессии (см. (83)). Оценка (А.б) — это частный случай неравенства Чернова [45). Более точные и более общие результаты приведены в работе Феллера 182), Фиг. АЛ. Геометрическая интерпретация функции Е(А, Р). Сумму вида С„а г-е можно оценить, если положить Р = 1/(а+ 1), 1;) = а/(а+1) и учесть, что Гчя ФП и ~~'„С,',а'=(а+1)" ~„,С'Р" Я'=(а+ 1)" ) С„'Р'9" ' (А.й) В каждом из неравенств (А.4) — (А.7) содержится некоторый множитель, лишь слабо зависящий от т, и множитель С~" или С„"Р "(7". Биномиальный коэффициент С„"" можно оценить, используя выражение (А.1) и неравенства (А.2) и (А.З); главным членом в этих оценках будет произведение Х вЂ” х"р-~'".
Для вычисле- ниа при больших значениях п полезны следующие формулы: — 1од(Х ~'"!т ' )= — Х1одХ вЂ” р1од!х=Н(Х), (А.10) где энтропия Н (х) = — х 1од х — (1 — х) 1од (1 — х) (А.11) и — — )од(Р. и ' Р "Я~)= = — Н (Х) — Х 1од Р— ц 1од Я = — Н (Х) + Н (Р) + +(Р— Х)1одр+ (!х — Я) !ода. Но !х — Я= — (Р— Ч* г!Н (х)р!х = Н' (х) = 1од ((! — х)/х], и, следовательно, — — „1о2Ь "р, ~Р Я"')=Е(Л. Р), (А.12) где Е()», Р)=Н(Р)+ Р— Р) Н'(Р) — Н(а). (А.)З) Как показано на фиг. А.1, этому выражению может быть дана интересная геометрическая интерпретация. Соотношении (А.!О) — (А.13) верны при любом выборе основания логарифмов, конечно, при условии, что во всех соотношениях используется одно и то же основание. В приложении Б приводится краткая таблица для случая обычных логарифьюв (по основанию !О).
Более полные таблицы, использующие логарифмы по основанию 2, приведены в работах [64, 79). Приложение Б. Краткая таблица значений энтропии (по основанию 10) и ее первой производной Р Н ЙХ(Х)/а(Х ОООО) .ООООЗ оооог,ооо)о ЪОООЭ .ООО)5 ООООа «ООО)9 ООООЗ >ООО24 00006 00028 00007 00032 00008 00036 00009 000«0 00010 >000«« З,ОООО «ебРРО 4>$229 а.3979 «.ЭО)О «,22)а ««1549 а,оаа9 а.о«57 4>ОООО ООО) «ООО»» Я,ОООО ОООЗ «ОООаЭ Э,ЬРЬР 0003 «00119 3«52)Т ооо» ,оо)53 5.5978 ОООЗ .ОО)67 5 ° ЗООВ 0006 е00219 3 ° 2216 ОООТ «00251 Э 15«6 оооа ,оогвг З.оаьа 0009 «00313 3 0«54 0010 ° 00349 2 9996 О) «02432 1 9956 Ог «О«гЗВ )«8902 ОЭ «056$2 1«ЗОР7 04 «0729« 1 ° 3802 0$ ° ОВЬ21 1«2768 06 09857 1 ° 1950 07 «110151 ° 1254 08 ° 12107 1 0607 09 ° 13139 1 0048 10 ° 14116 Ое9542 001 е003»3 2«9996 002 «00627 2*6981 003 «00667 2>$216 004 «01133 2«3962 00$ ° 01387 2 2989 006 «01593 2 2192 007 е01811 2 ° 1519 008 02024 2 093« 009 02230 2 0418 010 «02«Э2 1 ° 9956 ,ООО«8 5.956«8 00052 3 9208 00056 3 6880 00060 3>6338 00064 3 6238 .оооаа 3,7956 ОООТ) 3 7Ь95 ОООТЗ 3 7««7 ОООТ9 Э 7212 ° 00083 3 Ь969 011 «02БЗО 012 0262Э 013 «03013 014 «03199 015 03362 016 03543 о)7 о57«о О)6 ОЭР)5 019 О«088 020 ОЯ256 1«9536 1«915Ь 1«ВВО« 1>ВЯ77 ) 8173 1 7869 1 7621 1«7368 1 7129 1 ° 6902 11 ° 15049 Оа9080 12 ° 15935 0 8653 13 ° 1Ь781 0>6256 14 1Т587 0 7884 15 ° 16358 0«7533 16 19095 0 7202 17 ° 19т99 0 8886 )В >20«72 0.6565 19 ° 2111Ь 0>6297 20 21732 0«6021 00)) ° ООЗТЗ 0012 «00403 0013 00432 0014 «00460 0015 ° 00489 0016 00517 001Т 00545 0018 «ОО572 0019 00599 0020 ° 00627 2 9581 2 9203 2 ° 6655 2 05ЭЗ 2 ° 6233 2 ° 7932 2>ТЬВВ 2 ° 7«ЗР 2 ° 720« 2«6981 00066 Ъ 6777 ° 00090 3 6575 ° 0009« 3 6382 ° 00097 3 6197 00101 3>6020 ° 0010$3 5849 ° 00108 3 $685 ° 00112 Ъ 5527 ° 00115 3 5375 00119 3 5227 021 ° 0««26 1 6686 022 ° ОЯ592 1>8479 023 ° 0«ТЗЗ 1 ° 6262 024 0«917 1 6092 02$ ОЪОТ7 1«5911 огь .05255 1.5736 027 05392 1 5567 огв .о55«7 1 ° Ъао5 029 85700 1 ° 5248 030 05852 1 ЗОРТ 21 ° 22321 0 57$>« 22 ° 22883 0 5«9Т 23 .23«гО 0«5246 2« ° 23933 0 5006 2$ 2«422 0>4771 26 24686 0 45«5 27 25ЭЭ) 0 4320 28 ° 25Т52 0 4102 29 26)51 О 3669 50 ° 26530 О>3680 0021 00653 0022.
00680 0023 «00707 0024 «00733 0025 а007$9 оогь >оо)65 ООг) >ООЬ)) 0026 00636 оо)9 >ооваг ооэо .ооав) 2 8789 2>6566 2 Ь373 2 Б)ВТ 2 6010 2 ЗВЭ9 2 За)Э 2 5516 2 ° ЗЭЬЭ 2 ° 5216 0 3«ТЗ 0 327« 0 Э078 0 2881 О 2686 0 249Р 0 2511 0 212Ь 0 1943 0 1761 031 ° 06002 1 «950 032 ОЬ151 1 ЯВ07 ОЗЗ 06298 1 «6ЬР ОЗЯ 0644« 1 4535 055 06589 1 4405 036 ° 06732 1 4278 037 06874 1 ° »154 ОЭВ ° 07015 1 ° 4034 039 07155 1 ° 3917 040 07294 1 ° 3802 0031 00912 2 ° 5073 0032 00937 2 4935 0033 00962 2 4801 ООЪЯ 00967 2 4670 0035 01011 2 Я%44 0036 010Э6 2 4421 0037 010ЬО 2 ° 4302 0038 0108а 2 ° 4186 0039 01109 2 4072 0040 01133 2 ° 3962 .ОО)22 Ъ.ЪОВЪ ° 00126 3 4947 .оа)29 3.«а)э ° 00133 Э 4684 0013Ь Э 4556 00140 3 4435 ° 00143 3 «316 00146 Э 4201 ° 00150 3 4088 0015Э 3 ° 3978 00031 00032 ОООЗЗ ОООЭЯ 00035 00036 00037 00038 00039 00040 О ° 1561 О 1402 0 1224 О 10»7 0 0872 0 0696 0 0522 0«0348 0 017« О 0000 Я1 ° 29396 42 ° 295ЯЪ «3 ° 29676 44 ° 29790 45 ° 29885 «Ь ° 29964 47 >Э0025 40 ЪОО68 49 ° 3009« 50 ° 30103 041 ОТ«31 1 ° 3690 042 07568 1 ° 3581 043 07703 1 Э«74 044 07637 1 ° 3370 045 07970 1 3268 04Ь 08102 1 ° 3168 047 08234 1 3070 048 08364 1 ° 2974 049 08493 1 2880 оЗо оььг) 1.2768 0041 0115Б г 3854 0042 01180 2 ° 3749 0043 01204 2 7647 00«4 01226 2 354Ь 004$ 01251 г 3448 0046 0127» 2 3352 0047 >01298 2 3259 ОО»В 01321 2 Ъ167 Оо«9 013»4 г 3077 0050 01ЭЬ7 2 2969 ООО»1 00157 3>3870 00042 00160 3 Э766 0004Э 00163 3 ° 366Э 00044 00167 3 35Ь4 00045 ° 00170 Э Э4Ьб 00046 00173 3 3370 ООО«7 ОО)77 Ъ 327) ооо«8 .оо)ао З.з)аь 00049 00183 3>309Ь ОООЪО .ОО)87 Ъ.ЭООВ 0%1 >087Я9 1 2697 052 >088)5 1 ° 2608 ОЗЭ 09001 1*2$21 054 09126 1 ° 2435 055 09250 1 2351 056 09373 1 2266 057 0949$ 1 ° 2186 056 09617 1 2106 0$9 «097ЗТ 1 2027 060 09857 1 ° )950 00$) 01390 2 ° 2902 0052 01»)3 2 261Т оо33 .о)«эь г.г)э» 005« >01«58 2 ° 2653 005$ 01481 2 2572 00$6 >01%0« 2 249« 0057 0152Ь 2 ° 241Ь ООЗВ 01548 2 23«0 0059 ° 01571 2 22ЬЬ Ооьо 0159$ г 2192 00051 00052 00053 0005« 00055 00056 00057 00058 00059 00060 00190 ° 00193 00197 ° 00200 ° 0020Э ° 0020Ь ° 00210 ° 00213 ° 00216 00219 3 ° 2922 3 ° 2636 3 275% Э«2874 3 2594 3 25)Ь 3 ° 24Э9 Э 23ЬЗ Ъ ° 2289 3 2216 00011 00012 00013 00014 00015 0001Ь 00017 00018 00019 00020 00021 00022 00023 0002Я 00025 Ооога 00027 00028 00029 00030 Р Н а)Н(Х)/а(Х Р Н )(Н(Х)(ИХ Р Н ИН(Х)/>(Х 31 26867 32 27225 35 27542 34 27840 28118 ЗЬ ° 28376 37 ° 28616 38 ° 28840 Э9 ° 29043 40 ° 29229 Приложение В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
