Новиков Ф.А. Дискретная математика для программистов (860615), страница 42
Текст из файла (страница 42)
Пусть требуется передавать через этот канал потоксообщений, каждое длины п. Рассмотрим следующее кодирование: F(a): = ааа(то есть каждый разряд в сообщении утраивается) и декодирование F~1(abc): =: — a + b + с > 1 (то есть разряд восстанавливается методом «голосования»).
Этокодирование кажется помехоустойчивым для данного капала, однако на самомделе это не так. Дело в том, что хотя можно предполагать, что при передаче сообщения длины Зп возможно не более 3 ошибок типа замещения разряда, но местаэтих ошибок совершенно не обязательно распределены равномерно по всему сообщению. Ошибки замещения могут произойти в соседних разрядах, и методголосования восстановит разряд неверно. Чтобы метод голосования сработал,вместо одного сообщения длины Зп придётся передать 3 сообщения длины га,то есть уменьшить втрое скорость передачи потока сообщений через капал.2236.3. Помехоустойчивое кодирование6.3.2.
Возможность исправления всех ошибокПусть Eg — множество слов, которые могут быть получены из слова s в результате всех возможных комбинаций допустимых в канале ошибок тина 6, то естьs G S с A*, Eg с В*. Если s' е Eg, то кратчайшую последовательность ошибок,которая позволяет получить из слова s слово s', будем обозначать Е6(,ч,я'). Заметим, что таких последовательностей может быть несколько. Другими словами,Esa = {s' е В* | 3Es(s,s')}.Количество ошибок в кратчайшей последовательности E6(s,s')обозначим| £ I ( 5 ( S , S ' ) | . ЕСЛИ характеристика канала подразумевается, то индекс <5 пе указывается.Пример Пусть 6 = (2,1,1) для слов длины 2. Тогда10)| = 2, причёмсуществует несколько различных кратчайших последовательностей ошибок, в1 Oi—• 1 л л li-»0 ~ г.
г.-. 0>->е л еп—>0 1 „ Г11 е>—>0 Г11 „ 0>—>ечастности: 01 —• 11—> 10; 01 —> 1 —• 10; 01 —• 010 —• 10.Чтобы существовало помехоустойчивое кодирование F с исправлениемвсех ошибок типа 5, необходимо и достаточно, чтобыЧ si,s2 G SП EsS2 = 0 ) .ТЕОРЕМАДОКАЗАТЕЛЬСТВО[ =>• ] Если кодирование помехоустойчивое, то EsSl П Е832 = 0, иначе F~l невозможно было бы определить как функцию.[ < = ] По теореме 1.2.7 из условия Vsi,s2 € S (Е^ П Е53<2 — 0 ) следует, чтосуществует разбиение Ъ = {Ba}ses множества В*, причём Vs G S (Eg с Ва). По ч_разбиению Ъ требуемая функция F - 1 : В*S строится следующим образом:if s' G Bs then F~1(sf): = s end if.•Пример Рассмотрим канал, в котором в любом передаваемом разряде происходит ошибка типа замещения с вероятностью р, причём замещения различныхразрядов статистически независимы. Такой канал называется двоичным симметричным.
В этом случае любое слово s е Е% может быть преобразовано в любоедругое слово s' G Е2 замещениями разрядов. Таким образом, Vs (E s = £ £ )> иисправить все ошибки в двоичном симметричном канале невозможно даже присколь угодно малом р > 0.Будем говорить, что F является кодированием с исправлением р ошибок типа 5,если существует декодирование F - 1 такое, чтоVs е S (ys'eE6F(s)(\Es(F(s),s')\<p^F-1(s')= s)).Пример Пусть S = (1,0,0) для слов длины п. Метод голосования, рассмотренный в примере предыдущего подраздела, является кодированием с исправлениемодной ошибки типа замещения, но не является кодированием с исправлениемвсех ошибок при п > 1.224Глава 6.
Кодирование 2246.3.3. Кодовое расстояниеНеотрицательная функция d(x,у): М х М —> М+ называется расстоянием (илиметрикой) па множестве М, если выполнены следующие условия (аксиомы метрики):1. d(x, у) = 02. ф : , у ) =х = у.ж).3. d(x, у) ^ d(x, z) + d(y, 2).Множество {у | d(x, у) ^ р} называется шаром, или метрической окрестностью,с центром в ж и радиусом р.Пусть некоторый канал имеет характеристику S. Рассмотрим функциюDpf[min\Е6(0',0"}\,[+00,если 0" е Е50„если 0" £ Ер,.Эта функция называется расстоянием Хэмминга1.ЗАМЕЧАНИЕМы рассматриваем симметричные ошибки, то есть если в канале допустима ошибка 0 >—>• 1,то допустима и ошибка 1 —i > 0.ЛЕММАВведенная функция d& является расстоянием.ДОКАЗАТЕЛЬСТВО[ 1 ] ds{0',0") = 00' = 0", поскольку длина кратчайшей последовательности преобразований равна пулю тогда и только тогда, когда слова совпадают.[ 2 ] ds{0',0") = d,s(0",0'), поскольку ошибки симметричны, и из последовательности Е6(0',0") можно получить последовательность Е8{0",0'), применяяобратные ошибки в обратном порядке.[3] ds{0',0") < ds{0',0'") + ds(0",0"'), поскольку конкатенация последовательностей Е6(0',0"')и Е5(0"',0") является некоторой последовательностью,преобразующей 0' в 0", a ds(0',0") является длиной кратчайшей из таких последовательностей.•Пример Расстояние Хэмминга в Е%.
Пусть 6 = (п, 0,0), то есть допускаютсятолько ошибки типа замещения разрядов. Рассмотрим слова 0' = Ъ\... Ь'п и 0" —— ЪЧ .. .Ь". Тогда d(0',0")Def71= Y^iKЩ)- То есть расстоянием Хэмминга междуt=iбитовыми шкалами одной длины является число несовпадающих разрядов.1Ричард Весли Хэммипг (1915-1998).2256.3.
Помехоустойчивое кодированиеЗАМЕЧАНИЕВ последней формуле, так же как и в других местах этой книги, используется неявноеприведение false 1-4 О, true 1—• 1.Пусть а = (ai —•1— схема алфавитного кодирования, a d — некотораяметрика на В*. Тогда минимальное расстояние между элементарными кодамиd(a) =mind(Pi,Pj)называется кодовым расстоянием схемы а в метрике d.Алфавитное кодирование со схемой а = (а^ —» А)™=1 и с кодовым расстоянием Хэмминга d(a) — ^min ^(3") является кодированием с исправлением р ошибок типа S тогда и только тогда, когда d(a) > 2р.ТЕОРЕМАЕсли можно исправить ошибки в каждом из кодовых слов, томожно исправить ошибки и во всем сообщении.
Поэтому достаточно рассматривать только кодовые слова. Заметим, что множестводля капала, которыйдопускает не более р ошибок типа <5,— это шар радиуса р с центром в х. Такимобразом, Ер, П Ер„ = 0d(a) > 2р. По теореме 6.3.2 условие Е% П Е%„ = 0равносильно существованию требуемого декодирования.•ДОКАЗАТЕЛЬСТВОПример Рассмотрим схему равномерного кодирования а = (а* —• А)п=1> г Д е\/г (\Pi\ — rn), m ^ [log2(n - 1)J + 1. Такая схема может исправлять h ошибоктипа замещения в тп разрядах, если и только еслито есть если и только если любые два кодовых слова различаются не менее чемв 2h разрядах.6.3.4.
Код Хэмминга для исправления одногозамещенияОчевидно, что для помехоустойчивости вместе с основным сообщением нужнопередавать какую-то дополнительную информацию, с помощью которой в случае ошибок можно восстановить исходное сообщение. При этом нельзя считать,что дополнительная информация пе подвержена ошибкам. Задача состоит в том,чтобы определить, какую дополнительную информацию следует передавать, чтобы её объём был минимальным, а процедуры кодирования и декодирования повозможности простыми.Рассмотрим построение кода Хэмминга, который позволяет исправлять одиночные ошибки типа замещения. Пусть сообщение а = а\ .
. . а т кодируется словомР = Ь\ ... bn, п > т. Обозначим к:—п — т. Пусть канал допускает пе более однойошибки типа замещения в слове длины п.226Глава 6. Кодирование 226ОТСТУПЛЕНИЕРассматриваемый случай простейший, по одновременно практически очень важный. Таким свойством, как правило, обладают внутренние шины передачи данных в современныхкомпьютерах.
При этом часто применяют аппаратно реализуемый метод повышения надёжности, который называется контролем чётности. Суть метода заключается в том,что к шине добавляется дополнительный разряд, значение которого определяется припередаче как двоичная сумма остальных разрядов. Таким образом, общее количествоединиц, передаваемых по шине, всегда чётно. Если при приёме переданное количествоединиц оказывается нечётным, диагностируется произошедшая ошибка.
Контроль чётности позволяет обнаружить одиночную ошибку типа замещения разряда, но не позволяетеё исправить.При заданном п количество дополнительных разрядов к подбирается таким образом, чтобы 2к ^ п + 1. Имеем:on2 fc ^ П + 1 = »п+1on^ 2п~к=>г ^ 2т.п+1Пример Для сообщения длиной т = 32 достаточно к = 6 дополнительныхразрядов, поскольку 64 = 26 > 32 + 6 + 1 = 39.Определим последовательности натуральных чисел в соответствии с их представлениями в двоичной системе счислеиия следующим образом:V\: = 1,3,5,7,9,11,...
— все числа, у которых разряд 1 равен 1;V2 : = 2,3,6,7,10,...— все числа, у которых разряд 2 равен 1;Уз: = 4,5,6,7,12,...— все числа, у которых разряд 3 равен 1,и т. д. По определению последовательность 14 начинается с числа 2к~1. Такжерассмотрим последовательности Vfc', где V^ получается из Vk отбрасыванием первого элемента. Рассмотрим в слове Ь \ . . . Ь п к разрядов с номерами 2° = 1, 21 = 2,22 = 4, ...2 f c _ 1 .
Эти разряды назовём контрольными. Остальные разряды, а ихровно т , назовём информационными. Поместим в информационные разряды всеразряды слова а\... ат как они есть. Контрольные разряды определим следующим образом:6Х; = 63 + 65 + bj + . . . , то есть сумма всех разрядов с номерами из V/;62 : = Ьз + 6б + &7 + • • • j то есть сумма всех разрядов с номерами из V2;64 : = 65 ++ Ь7 + . . . , то есть сумма всех разрядов с номерами из V^';и вообще, Ь2з-1 : = Y1причём сложение выполняется по модулю 2.
Пусть поievjеле прохождения через капал получен код с\... сп, то есть с\... сп : = С {by... bn),причём37 ((cI = bI V d = 67) & V i / / (Ci = bi)).Здесь I — номер разряда, в котором, возможно, произошла ошибка замещения.Пусть это число имеет следующее двоичное представление: I = ц ... i\. Определим число J = ji...следующим образом:; = ci + сз + С5 + С7 + .
. . , то есть сумма всех разрядов с номерами из V\;32 = С2 + сз + се + С7 + . . . , то есть сумма всех разрядов с номерами из V2;j3 : = С4 + С5 + cq + С7 + . . . , то есть сумма всех разрядов с номерами из V3;и вообще, jp-.= X) c<z> г Д е сложение выполняется по модулю 2.яеУр6.4. Сжатие данныхТЕОРЕМА227В указанных обозначениях I = J.Э Т И числа равны, потому что поразрядно равны их двоичныепредставления. Действительно, пусть i\ = 0. Тогда I £ Vi, и значит,ДОКАЗАТЕЛЬСТВОji = ci + с3 + с5 + ... = Ьх + Ьз + Ь5 + ... = 0по определению разряда Ь\.
Пусть теперь i\ = 1. Тогда I е Vi, и значит,ji = Ci + с 3 + с 5 + . . . = fei + 6 3 + 65 + . . . + bx + . . . = 1,так как если в сумме по модулю 2 изменить ровно один разряд, то изменится изначение всей суммы. Итак, i\ = j\. Аналогично (используя последовательностиV2 и т. д.) имеем г2 =и т. д. Таким образом, / = ,7.•Отсюда вытекает метод декодирования с исправлением ошибки: нужно вычислить число J.
Если J = 0, то ошибки нет, иначе c j : = cj. После этого из исправленного сообщения извлекаются информационные разряды, которые уже несодержат ошибок.ЗАМЕЧАНИЕУниверсальный метод построения наилучшего помехоустойчивого кодирования для произвольного тп и произвольного типа канала S неизвестен. Однако для большинства встречающихся на практике комбинаций m и 5 задача построения кодирования с исправлениемвсех ошибок решена.6.4. Сжатие данныхМатериал раздела 6.2 показывает, что при кодировании наблюдается некоторыйбаланс между временем и памятью. Затрачивая дополнительные усилия при кодировании и декодировании, можно сэкономить память, и наоборот, пренебрегаяоптимальным использованием памяти, можно существенно выиграть во временикодирования и декодирования. Конечно, этот баланс имеет место только в определённых пределах, и нельзя сократить расход памяти до пуля или построитьмгновенно работающие алгоритмы кодирования.
Для алфавитного кодированияпределы возможного установлены в разделе 6.2. Для достижения дальнейшегопрогресса нужно рассмотреть неалфавитное кодирование.6.4.1. Сжатие текстовДопустим, что имеется некоторое сообщение, которое закодировано каким-тообщепринятым способом (для текстов это, например, код ASCII) и хранится в памяти компьютера. Заметим, что равномерное кодирование (в частности, ASCII)не является для текстов оптимальным. Действительно, в текстах обычно используется существенно меньше, чем 256 символов (в зависимости от языка —примерно 60-80 с учётом знаков препинания, цифр, строчных и прописныхбукв). Кроме того, вероятности появления букв различны, и для каждого естественного языка известны (с некоторой точностью) частоты появления букв втексте.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
