Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 79

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 104 >> Следующая

(1 ^ V < I) и Уй ... VI — его двоичная запись.
т входе
не выходе
^/*2 ***А
Рис. 15
Последовательность 1, 3, 5, 7, 9,... содержит все числа Ус Уі = 1.
Последовательность 2, 3, 6, 7, 10, ... содержит все числа Ус У2= 1.
Последовательность 4, 5, 6, 7, 12,... содержит все числа У с Уз — 1.
Последовательность 2к~1, 2Л-‘ + 1, ... содержит все числа У с Уь — 1.
Первыми членами этих последовательностей являются числа
1=2°, 2 = 2* 2*“\
т. е. степени двойки, причем 2*-1 < /, а 2к 5* / 4* 1,
Члены набора рь ..., р*, у которых ипдекс ? принадлежит множеству (1, 2, ,.2Ь"1), называются контрольными членами, остальные — информационными. Легко видеть, что контрольных членов будет к, а информационных I — к = тп.
Сформулируем теперь правило построения набора р!,.. р1 по набору ах,,, ат. Сначала определяются иифор-
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ 291
мационные члены
Зз = «1,
3s = аг»
Зб = ОСз,
• * » > I
Таким образом, набор из информационных членов, расположенных в естественном порядке, совпадает с набором cti... «т. Далее определяются контрольные члены
3i e h + 3s + Зт + • ? ? (mod 2),
Зг = Рз Т рй + рт + ... (mod 2), р4 = р5 + 3« + Зт + * ..(mod 2),
Здесь суммирование ведется по последовательностям, построенным выше. В этих формулах правые части, очевидно, состоят из информационных членов, которые нами уже определены. Обозначим через //] множество всех построенных наборов 3*?* ? Зь
II. Обнаружение ошибки в кодах Хэмминга. Пусть (рх ... р/)(= Н] и при передаче кода 3,... р; произошла ошибка в 5-м члене. Тогда на выходе канала было принято слово Р1 .. ? Зь где
З1 * ? • Рг ~ Зт • * • Рз * *. Рь>
Пусть 5 = 5„..,51 — запись числа 5 в двоичном счисле-вии. Покажем, как можно по коду Р* . .. рг найти число 5. Рассмотрим число 5' = 5\ .. . 51} где:
?1 = Р1 + Рз + Рг, Т- р- + - • • (1-я последовательность),.
?2 = Рз + Рз + Рй + Р? + . * - (2-я последовательность),.
-53 = Р4 + Рб + Ро + Р7 + ? * • (3-я последовательность),
Утверждается, что 5 = 5'. В самом деле, если 54 = 0, то 5 не принадлежит 1-й последовательности и тогда
Рх + Рз + Р& + р7 + * ? * = Р1 + Рз + РБ + Р7 Т- * ? . = О,
поэтому 51 = 0; если 51 = 1, то 5 принадлежит 1-й последовательности и тогда
Рх + Рз + Р& + Р7 3- • * * ” 1 + Рх + Рз + Р5 + Р7 + ,,. =» ^}
поэтому 5* = 1, Таким образом, 5! = 514 19 *
292
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Аналогично доказывается, что — 321 # * *!
Отсюда следует, что $ =
Если при передаче ошибки не произошло, то, очевидно, Б' «= 0. Значит число 5' позволяет узнать, произошла ли ошибка при передаче и, если произошла, то найти номер члена 5, который исказился помехой. В последнем случае производим коррекцию ошибки: член 0й заменяем па 0з*
III. Декодирование. Этот шаг состоит в построении исходного сообщения а!...а™ по коду 01 .,„07. Для этого, очевидно, достаточно взять информационные члены в 01... 0/.
Пример 14. Построить самокорректирующийся код для т = 4. Наименьшее число /, удовлетворяющее неравенству
24<7ТТ*
будет 1 = 7, и тогда к = 3. В соответствии с этапом I получаем самокорректирующийся код. Результат этого построения представлен в табл. 1, в которой контрольные
члены помечены звездочкой.
Таблица 1
1* 2* S 4* 5 6 7 1* 2* S 4* Б 6 7
0 0 0 0 0 0 0 1 1 1 0 0 0 0
1 1 0 1 0 0 1 0 0 1 1 0 0 1
0 1 0 1 0 1 0 1 0 1 1 0 4 0
1 0 0 0 0 1 1 0 4 1 0 0 4 1
1 0 0 1 1 0 0 0 1 1 1 1 0 0
0 1 0 0 1 0 1 1 0 1 0 1 0 4
1 1 0 0 1 1 0 0 0 1 0 1 4 0
0 0 0 1 1 1 1 1 1 1 1 4 4 1
В этой таблице сначала в столбцы с номерами 3, 5, 6 и 7 (информационные члены) вписываются сверху вниз наборы 0000, 1111. Затем по формулам
0i = 0s + 05 + 07 (mod 2),
0а “ 0s + 0в + 07 (mod 2),
04 = 05 + 0в + 07 (mod 2)
заполняются столбцы с номерами 1, 2 а 4.
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
298-
Пусть на вход капала поступил код 0110011, и в нем источник помех исказил 5-й член (5 = 5). Тогда на выходе мы получим 0110111. Вычислим номер члена, в котором произошла ошибка. Мы имеем
™ Р1 + 03 “Ь Ра + 07 ”*0 + 1 + 1+1~= 1Л
&а — 0а + 0а + 0е + 07 5=11 + 1 + 1 + 1
“ Р* + Рь + Ре + Р? в 0 + 1 + 1 + 1 — 1.
Следовательно, 8' = 101, т. е. 8' = 5. Мы обнаружили член, в котором произошла ошибка, и 5"= 5.
В заключение остановимся на выяснении геометрических свойств кодов Хэмминга.
Будем рассматривать единичный /-мерный куб как метрическое пространство, в котором для любых двух точек Р' “ (Рь * • • | Рг) и 0" = (01, ,.., 0*) расстояние р(Р\ Р*} определено следующим образом:
р{Р'.«-21Й-Й|.
? 1=1
Очевидно, р(Р', Р*) есть число координат, в которых различаются наборы р' и р",
Теорема 9. Для любых наборов р' и р" таких, что Р' Ф р" и р" е Я|, имеет место р(Р', р") 5* 3.
Доказательство. Утверждение будет доказано, если исключить два случая: а) р(р', Р") — 1; б) р(Р', 0" ) = = 2. В самом деле, если р(0 , р")= 1, то возможна единичная ошибка, при которой код 0' перейдет В КОД 0" и, если р(0', 0")=2, то существует такой набор р'", что р(Р', р'//)= р(р,Я, Р")=1, т. е. возможны переходы при единичных ошибках кодов р' и 0" в код р'",
Следовательно, в обоих случаях на выходе капала возможна ситуация, в которой нельзя установить, какой из кодов рг или р/Л фактически был передан, что противоречит самокорректируемости кода Н\. Теорема доказана.
Предыдущая << 1 .. 73 74 75 76 77 78 < 79 > 80 81 82 83 84 85 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed