Дискретная математика (998286), страница 31
Текст из файла (страница 31)
А эта последовательность хранится в экземплярах локальной переменной у, соответствующих рекурсивным вызовам процедуры Нийпап. П 172 Глава 6. Кодирование Пример Построение оптимального кода Хаффмена для п = 7. В левой части таблицы показано изменение массива Р„а в правой части — массива С, Позиция, соот- ветствующая текущему значению переменной,у, выделена полужирным начерта- нием.
Цена кодирования составляет 0.20 х 2+ 0.20 х 2+ 0.19 х 3+ 0.12 х 3+ 0.11 х 3+ 0.09 х 4+ 0.09 х 4 = 2.78, что несколько лучше, чем в кодировании, полученном алгоритмом Фано. 6.3. Помехоустойчивое кодирование Надежность электронных устройств по мере их совершенствования все время возрастает, но, тем не менее, в их работе возможны ошибки, как систематические, так и случайные.
Сигнал в канале связи может быть искажен помехой, поверхность магнитного носителя может быть повреждена, в разъеме может быть потерян контакт. Ошибки аппаратуры ведут к искажению или потере передаваемых или хранимых данных. При определенных условиях, некоторые из которых рассматриваются в этом разделе, можно применять методы кодирования, позволяющие правильно декодировать исходное сообщение, несмотря на ошибки в данных кода.
В качестве исследуемой модели достаточно рассмотреть канал связи с помехами, потому что к этому случаю легко сводятся остальные. Например, запись на диск можно рассматривать как передачу данных в канал, а чтение с диска — как прием данных из канала. 6.3.1. Кодирование с исправлением ошибок Пусть имеется канал связи С, содержащий источник помех: Я вЂ” +У 8еА',УеВ", где Я вЂ” множество переданных, а Я' — соответствующее множество принятых по каналу сообщений. Кодирование Р, обладающее таким свойством, что Я вЂ” + К вЂ” + К' — + Я, Ув е э', Р 1(С(Р(в))) = а; 0.20 0.20 0.23 0.37 0.40 0.80 0.20 0.20 0.20 0.23 0.37 0.40 0.19 0.19 0.20 0.20 0.23 0.12 0.18 0.19 0.20 0.11 0.12 0.18 0.09 0.11 0.09 0 1 00 01 10 1 00 01 10 11 01 10 11 000 11 000 001 001 010 011 10 11 000 010 011 0010 0011 6.3. Помехоустойчивое кодирование называется помехоустойчивым, илн самокорректирующимся, или кодированием с исправлением ошибок.
Вез ограничения общности можно считать, что А = В = (О, 1), и что содержательное кодирование выполняется на устройстве, свободном от помех. 6.3.2. Классификация ошибок Ошибки в канале могут быть следующих типов: ь 0 + 1, 1 -+ 0 — ошибка типа замещения разряда; ~ 0-+.Л, 1-+ Л вЂ” ошибка типа выпадения разряда; ь Л -+ 1, Л -+ 0 — ошибка типа вставки разряда. Канал характеризуется верхними оценками количества ошибок каждого типа, которые возможны при передаче через канал сообшения определенной длины.
Общая характеристика ошибок канала (то есть их количество и типы) обозначается Л Пример Допустим, что имеется канал с характеристикой б = (1, О, О), то есть в канале возможна одна ошибка типа замещения разряда при передаче сообщения длины и. рассмотрим следующее кодирование: р(а): =ааа (то есть каждый разряд в сообщении утраивается) и декодирование Г '(аЬс): = а+ Ь+ с > 1 (то есть разряд восстанавливается методом еголосованияь). Это кодирование кажется помехоустойчивым для данного канала, однако на самом деле это не так. Дело в том, что при передаче сообшения длины Зп возможно не более 3 ошибок типа замешения разряда, но места этих ошибок совершенно не обязательно распределены равномерно по всему сообщению.
Ошибки замещения могут произойти в соседних разрядах, и метод голосования восстановит разряд неверно. 6.3.3. Возможность исправления всех ошибок Пусть Ев — множество слов, которые могут быть получены нз слова в в результате всех возможных комбинаций допустимых в канале ошибок б, то есть в Е Я С А", Ев С В'. Если в' Е Ев то та конкретная последовательность ошибок, которая позволяет получить нз слова в слово в', обозначается Ев(в, в').
Если тип возможных ошибок в канале подразумевается, то индекс б не указывается. ТЕОРЕМА Чтобы существовало помехоустойчмвое кодирование с исправлением всех ошибок, особ~одино и достаточно, чтобы Чв1, в2 е Я Е„п Е„= и, пю есть необходимо и достаточно, чтобы сущесгпвовало разбиение множества В' на множества В, Я В, = В', П В, = а), такое что ч'в е Я Е, С В,.
Доказательство Если кодирование помехоустойчивое, то очевидно, что Е„О Е„= ю. Обратно: по разбиению () В, строится функция р ': ч в' Е В, р '(в'): = в. П 174 Глава б. Кодирование 6.3.4. Кодовое расстояние Неотрицательная функция сг(х, р): М х М -г Ж«называется расстоянием (или метрикой) на множестве М, если выполнены следующие условия (аксиомы ме- трики): 1. с((х, у) = О «=ь х = у, 2. с((х,у) = с((р,х), 3. с((х,у) < с((х,а)+с((р,з), Пусть ~ппп1лцд д») ~Е (~3',13н) ~, ~+со, 13в Е Ег 33сс ф Ег Эта функция называется расстоянием Хэмминга. ЗАМЕЧАНИЕ Мы рассматриваем симметричные ошибки, то есть если в канале допустима ошибка О -+ 1, то допустима и ошибка 1 -+ О.
Введенная функция с(г является расстоянием. Действительно: 1. ссг(Д', (3') = О «=ь Д' = (3", поскольку ошибки симметричны, и из последовательности Е((3',(3н) можно получить последовательность Е(с3",д'), применяя обратные ошибки в обратном порядке. 2. с3гУ', Дн) = с(ь(33", (3в) по той же причине 3. сгг(13, (3л) < ссг(с3', 13т) + с(г((3", (3" ), поскольку Е(33с, (Зссс) 0 Е((3ссс, 13н) является некотоРой последовательностью, пРеобРазУющей )3' в 13", а с3г(/3', 13н) ЯвлЯетсЯ кратчайшей из таких последовательностей.
Пусть сг = (ас — + 33с);, — схема некоторого алфавитного кодирования, а с3— некоторая метрика на 23'. Тогда минимальное расстояние между элементарными кодами сс(а): = ппп с3(13с, с33) 1<с<1<л называется кодовьсч расстоянием схемы а. Пример Рассмотрим канал, в котором в любом передаваемом разряде происходит ошибка типа замещения с вероятностью р (О < р < 1/2), причем замещения различных разрядов статистически независимы.
Такой канал называется двоичным симметричгсьсм. В этом случае любое слово в е Ез может быть преобразовано в любое другое слово в' Е Ез" замещениями разрядов. Таким образом, ч'в Е, = Ез, н исправить все ошибки в двоичном симметричном канале невозможно. 175 6.3, Помехоуотойчивое кодирование ТЕОРЕМА Алфавитное кодирование со схемой а = (а; -б 33б)б, и с кодовым расстоянием об(а) = ШШ ибУ ~б' ) является кодированием с исправлением р ошибок типа 3 тогда и только тогда, когда дб(а) > 2р.
Докааатнпьство Е(х) — зто шар радиуса р с центром в х для канала, который допускает не более р ошибок типа 6. Таким образом, Еф) ПЕ((Г') = а 4=оде(а) > 2р по теореме 6.3.3. Пример к Расстояние Хзмминга в Ех: с((33' 33е): = х ((3б' т. )31 ). 6.3.5. Код Хзмминга для исправления одного замещения Рассмотрим построение кода Хзммиига, который позволяет исправлять одиночные ошибки типа замещения. Очевидно, что для исправления ошибки вместе с основным сообщением нужно передавать какую-то дополнительную информацию.
Пусть сообщение а = аг... а кодируется словом б3 = Ь1 . 6„, и > пг, Обозначим к: = н — пг. Пусть канал допускает не более одной ошибки типа замещения в слове длины н. ОТСТУПЛЕНИЕ Рассматриваемый случай простейший, но одновременно практически очень важный. Таким свойством, как правило, обладают внутренние шины передачи данных в современных компьютерах. При заданном и количество дополнительных разрядов й подбирается таким образом, чтобы 2" > н+ 1.
Имеем: 2 > н+ 1 =-.=.к — > 2" ==в — > 2~. ь 2" „ь 2" н+1 и+1 Пример Для сообщения длиной пх = 32 потребуется (г = 6 дополнительных разрядов, поскольку 64 = 2 > 32+ 6+ 1 = 39. Определим последовательности натуральных чисел в соответствии с нх предста- влениями в двоичной системе счисления следующим образом: 176 Глава 6. Кодирование 1и У~.=.1,3,5,7,9,11,... — все числа, у которых разряд Ж1 равен 1; ~ $'з.=2,3,6,7,10,... — все числа, у которых разряд Мю2 ранен 1; ~ Ьз -. =4,5, 6, 7, 12,... — все числа, у которых разряд 143 равен 1, и т.
д. По определению последовательность кь начинается с числа 2" '. Рассмотрим в слове Ь|... Ь„Ь разрядов с номерами 2о = 1, 2з = 2, 2з = 4, ... 2" '. Эти разряды назовем колтрольньиви. Остальные разряды, а их ровно пт, назовем информационными. Поместим в информационные разряды все разряды слова оз... а„как они есть. Контрольные разряды определим следующнм образом: Р Ь|: = Ьз Ю Ьз Ю Ьт Ю ° ., — то есть все разряды с номерами из Ъы кроме первого; ь Ьз . = Ьз Ю Ьв Ю Ьт Ю..., — то есть все разряды с номерами из Ъю кроме первого; ~ Ь4.
= Ьз Ю'Ье Ю Ьт Ю..., — то есть все разряды с номерами из Ъю кроме первого; и вообще, Ь„,:= ® Ь,. 'еь11(з' Ч Пусть после прохождения через канал получен код с~... с, то есть ст...с: =С(Ь~....Ь„), причем Э1, = ~ Ч'~1, =Ьо ГЬ, ~ь, Здесь 1 — номер разряда, в котором, возможно, произошла ошибка замещения.
Пусть зто число имеет следующее двоичное представление: 1 = и... в',. Определим число 1 = у~... и следующим образом; ~ Л:=сз Юсз Юсз ЮетЮ..., — то есть все разряды с номерами из Ъ~; а' Зз:= н Юсз Юге ЮстЮ..., — то есть все разряды с номерами из Ъз, Р Зз:=с4ЮсеЮсвЮЬтЮ..., — тоесть все разряды с номерами из Ъз, и вообще, т'р..— — ® сч. деье ТЕОРЕМА 1 = .1. Док затвпь о Эти числа равны, потому что поразрядно равны нх двоичные представления. Действительно, пусть в', = О.
Тогда 1 й Рн и значит, ут = с~ Ю сз Ю се Ю " . = Ьз Ю Ьз Ю Ьз Ю " . = 0 177 вхх Снятие данных по определению разряда Ьг. Пусть теперь зг = 1. Тогда 1 б Ъ;, и значит, Л =ст Юсз®сз®. =Ьг ЭЬз®ЬзЮ ЮЬ Ю =1, так как если в сумме по модулю два изменить ровно один разряд, то изменится и значение всей суммы. Итак, зг = тг. Аналогично (используя последовательности )гз и т. д.) имеем зз = гз и т. д. Таким образом, 1 =,У. П Отсюда вытекает метод декодирования с исправлением ошибки: нужно вычислить число,У. Если 1 = О, то ошибки нет, иначе сз. =сз. После этого из исправленного сообщения извлекаются информационные разряды, которые уже не содержат ошибок. 6.4. Сжатие данных Материал раздела 6.2 показывает, что при кодировании наблюдается некоторый баланс между временем и памятью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
