С.В. Яблонский - Введение в дискретную математику (1060464), страница 42
Текст из файла (страница 42)
Р„О, г — гэ)1, то сначала находят решение для (г, + ()-буквенного входного алфавита и вероятностей Рм ° ., Р.ю Р;+1 (Р;+~ О) ° Пусть Вз ..., В„, В„~»1 — элементарные коды для кода с минимальной избыточностью. Затем отбрасывают элементарный код В„+1 и для букв а,,+и...,а, берут в качестве элементарных кодов слова вида У (г +О В+, В+гВ' с Вг ' В~ +1В "ь Ф где ((В(' )) ... ((В~'~) и все слова В(' ), ...,Воо различны.
Очевидно, что построенный код имеет минимальную избыточность и удовлетворяет свойству префикса. $5. Самокорректирующиеся коды Здесь мы рассматриваем один частный случай равномерного кодирования. Пусть 6 (О, () — алфавит, содержащий два символа. Пусть далее (А„А„..., А.) — множество всех слов А ° =и,...а„в алфавите И, имеющих фиксированную длину и. (Здесь в 2".) Предположим, что в канале связи действует источник помех, который в словах из (А„..., А.), имеющих длину примерно т, может вызывать ошибки не более чем в Р символах.
Это значит, что двоичяая последовательность, полученная на выходе канала, отличается от двоичной последовательности, поступившей на вход этого канала, не более чем в р позициях. Совершенно ясно, что, если передавать исходное сообщение и,...а (без предварительного кодирования), то на выходе канала невозможно будет установить, какое сообщение фактически было передано. В связи с этим возникает вопрос, нельзя ли осуществить кодирование слов А нз множества (А„ ..., А.), т. е.
слов вида и,...а„, словами ~),...(), длины ( так, чтобы Ч. вт. ТЕОРИЯ КОДИРОВАНИЯ 2вз е по кодурл... рь полученному на выходе канала при передаче кода ру... рь можно было однозначно восстановить этот код, и, значит, исходное сообщение ау...а ? Коды, обладающие данным свойством, будем называть сампкорректиррющизуися кодами относительно рассматриваемого источника помех. Легко видеть, что существует тривиальное решение задачи.
Мы проследим это на простейшем источнике помех, для которого р 1, т. е. для которого возможно только искажение О - 1 или 1 — О. Искомый самокорректирующийся код получается путем утроения символов исходного кода ива,...а,. — а,ауаеивнлив .. а а а„. В самом деле, если при передаче этого кода произошла ошибка, то в некоторой группе а,а,ау искажен ровно один символ, а остальные группы переданы без ошибок, Это позволяет методом «гоетосовапия» осуществить коррекцию ошибки и восстановить код (и,и,ае...ух а и ), а значит и исходное сообщение (а,...а ).
Тривиальное решение не является корректным, так как длина кода здесь равна 1 = Зук и мы приходим к кодам, для которых данньш источник помех может вызывать ббльшее число ошибок, чем р, и тогда однозначно восстановить исходное сообщение не всегда будет возмон1но. Корректное построение самокорректирующихся кодов было осуществлено Хэннингом (40). Им подробно был разобран случай р = 1, к изложению которого мы и перейдем. Сообщения ае...а кодируются наборами ре...бн где 1 — длина кода и 1™ук+)с. Очевидно, что при наличии данного источника помех возможны следующие варианты получения кодов на выходе (см.
рпс. 15). Следовательно, число вариантов равно 1+1. Для того чтобы дополнительных разрядов в коде ру... ()у хватало для кодировки перечисленных 1 + 1 слуууаев передачи кода, необходимо, чтобы 2" ~1+1 или 2" (2У/(1+1). Из этих сообрануеннй выберем 1 как напменьшее целое число, удовлетворяющее неравенству 2 ~ 2'/(1+ 1). Ю Вмленне в лневреуную мвуемеунлу ч. гч. ткогия коднгования тес Дальнейшие построения будут состоять из трех этапов.
1. Построение кодов Хэмминга (описание алгоритма кодирования). Разобьем отрезок натуральных чисел (1, 2, ..., 1) на й последовательностей следующим образом: пусть У вЂ” произвольное натуральное число (1е, У<1) и У»... У,— его двоичная запись. Ркс. а Последовательность 1, 3, 5, 7, 9,... содержит все числа Уср, 1. Последовательность 2, 3, 6, 7, 10, ...содержит все числа г'с У, 1. Последовательность 4, 5, 6, 7, 12,...содержит все числа У с г",=1. Последовательность 2' ', 2" '+ 1, ... содержит все числа У с У, 1.
Первыми членами этих последовательностей являются числа 1=2', 2 2',...,2'', т. е. степени двойки, причем 2' ' < 1, а 2" >1+1. Члены 5, набора бо ..., ~)ь у которых нкдекс 1 принадлежит множеству (1, 2, ..., 2" '), называются контрольнььни членами, остальные — инЯормационныии. Легко видеть, что контрольных членов будет й, а ияформзционных 1 — й т. Сформулируем теперь правило построения набора ))~...
(» по набору а~...а . Сначала определяются инфор- ч. ъч. твовия ноднвоваеил мационные члены ()а = по аь 5, им Таким образом, набор из информационных членов, расположенных в естественном порядке, совпадает с набором а,...я . Далее определяготся контрольные члены 1 13+1 +Ь +...(шоб 2), ~ю = ~з+ йв+ ()т+...(пюд 2), ~)~ = ()з+ ~в+ ~~+... (шой 2), Здесь суммирование ведется по последовательностям, построенным выше. В этих формулах правые части, очевидно, состоят из информационных членов, которые вами уже определены.
Обозначим через Ы) множество всех построенных наборов р,...~ь П. Обнаружение ошибки в кодах Хэмм и нга. Пусть ((3, ... ~~) ен И) и при передаче кода (),...р, произошла ошибка з Я-и члене. Тогда на выходе Ф Ф капала было прнпято слово (5~... ()ь где 1;... К = (),... 1з ... ~ь Пусть о' Я~...Я, — запись числа Я в двоичном счислении. Покажем, как можно по коду()~... гч найти число Я. Рассмотрим число Б' = Ьь...
Ю„где: Р / о) = 1~ + (зз+ ~ь+ р7 + ... (1-я последовательность), Ф Ф л) Рз + (зз+ (зз + ()~ + .. (2-я последовательность), оз р4+ рз+ К+ ()~+ ... (3-я последовательность)„ Утверждается, что Я Я'. В самом деле, если Я, О, то 8 не принадлежит 1-й последовательности и тогда (),'+ ()з + К + К + ...
= (), + й, + (), +~, + ... - 0, Г поэтому Я, О; если Я, 1, то Я принадлежит 1-й последовательности и тогда (:+().+К+~.+ -1+(),+к+а,+(),+ ...-1. поэтому Ят 1. Таким образом, Ю, =Ю,. и ч. гч. твОРия кОдиРОВАния Ф Аналогично доказывается, что 84 34...ЯА ° ЯА.
Отсюда следует, что Я- Я'. Если при передаче ошпбви не произошло, то, очевидно, 8' О. Значит число 8' позволяет уэнать, произошла ли ошибка при передаче и, если произошла, то найти номер члена Я, который исказился помехой. В последнем случае производим коррекцию ошибки: член ))а эаменяем на рз. Ш. Декодирование. Этот шаг состоит в построении исходного сообщения 44,...44 по коду ()4...~О Для этого, очевидно, достаточно взять информационные члены в (), Пример 14.
Построить самокорректирующийся код для ш 4. Наименьшее число 1, удовлетворяющее неравенству 4 2 24 у — 14 будет 1 = 7, и тогда й 3. В соответствии с этапом 1 получаем самокорректирующийся код. Реаультат этого построения представлен в табл. 1, в которой контрольные члены помечены звездочкой. Таблица 1 В этой таблице сначала в столбцы с номерами 3, 5, 6 и 7 (информационные члены) вписываются сверху вниз наборы 0000, ..., Ш1.
Затем по формулам 34+()4+~т (шоб 2), ~4 34+ ~4+ ~т (шой 2), 3.-()4+3,+б, ( б г) заполняются столбцы с номерами 1, 2 и 4. ч. гт. теоРия коднРОВлння аез Пусть на вход канала поступил код 0110011, и в нем источник помех исказил 5-й член (3 5). Тогда на выходе мы получим 0110111. Вычислим номер члена, в котором произошла ошибка. Мы имеем ~ь ()ь+ Ь+ Рь+ ть О+ 1+ 1+ 1 1~ Бь - р'+ Ь+ р', + К -1+ 1+ 1+ 1- О, 'са 1а+ таь+ тае+ ()ь 0+ 1+ 1+ 1 1. Следовательно, Я' 101, т. е. Я'=5. Мы обнаружили член, в котором произошла ошибка, и Я'= Я. В заключение остановимся на выяснении геометрических свойств кодов Хзмминга. Будем рассматривать единичный 1-мерный куб как метрическое пространство, в котором для любых двух точек р' (ри ..., рь) и р" = (р,", ...,()ь) расстояние р(р', р" ) определено следующим образом.
р(1'ь1') - Х!()ь — 1ь~- Очевидно, р(5', ()") есть число координат, в которых различаются наборы р' и р". Теорема 9. Для любых наборов р' и р таких, что р' ч" р" и р', р" ен Н(, имеет место р(р', (1" ) > 3. Д о к а з а т е л ь с т в о. Утверждение будет доказано, если исключить два случая: а) р(р', р")= 1; б) р((1', р") = 2. В самом деле, если р(р', р")= 1, то возможна единичная ошибка, при которой код р' перейдет в код 5" н, если р((1', р" ) 2, то существует такой набор (), что р((1', ()'") р(р"', 5")=1, т.
е. возможны переходы прн единичных ошибках кодов 5' и р" в код 5'". Следовательно, в обоих случаях на выходе канала возможна ситуация, в которой нельзя установить, какой из кодов р' или р" фактически был передан, что противоречит самокорректируемости кода Н',. Теорема доказана. Пусть рь — некоторая точка единичного 1-мерного куба, Определение. Совокупность Ц'(~ь) точек (1 таких, что р(рь, р) < р, называется шаром с центром в 5' и радиусом р. Определение. Совокупность Р)'(рь) точек р таких, что р(р', р) р, нааывается сФерой с центром в р' и радиусом р, ч. «у. тиОРия кОдиРОВАния Очевидно, что если точка р' является «кодовой» точкой, то при передаче по каналу связи, в котором действует источник помех, вызывающий не более р ошибок, точка р«перейдет в точку р такую, что т.
е. точка )) будет принадле»кать шару 67())«) с центром в р«и имеющему радиус р. Отсюда вытекает следующий факт. Теорема 10. Для того чтобы множество Н, принадлежащее еди»шчнолсу 1-мерному кубу, было лсноэкеством, принадлежащил«самокорректирующемуся коду относительно источника помех, вызывающего не более р ошибок, необходил«о и достаточно, чтобы для любых р' и р" (р'чь()") из Н имело место Для доказательства лишь заметим, что условие р(р', Р")> 2р+1 эквивалентно тому, что шары Ц(~') и У,"())") с цептрамп в ))' и р" н имеющие радиусы р, но пересекаются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
