Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
40 §§ 17, 18), а сейчас постараемся выяснить, на что мы можем рассчитывать при минимальной избыточности, когда к каждому кодовому слову добавляется всего лишь один проверочный СИМВОЛ. Пусть OC1OC2. . .ап — двоичное кодовое слово. Выберем проверочный символ ссп+1 с таким расчетом, чтобы на его значение одинаково влиял каждый из символов данного слова. Это естественное требование будет выполнено, если, например, положить ап+1=а1-Ьос2-Ь. . .+а„ (mod 2). Тогда проверочный символ ап+1 будет равен нулю, если в кодовом слове OC1Ot2. . .ап содержится четное число единиц, и единице — в противном случае. Например, присоединяя таким образом проверочный символ к слову 1010, получаем слово 10100, а из слова 1110 получим слово 11101.
Нетрудно бидєть, что все удлиненные кодовые слова OCaOC2. . .cc;;an+1 содержат четное число единиц, т. е.
сса + а2+. . .+ос„ + ос„+1 = 0 (mod 2). (1)
Допустим, что в процессе передачи в удлиненное кодовое слово gc1oc2. . .anan+i вкралась одна ошибка (чли даже любое нечетное число ошибок). Тогда в искаженном слове OcJa2. . .CXrlCC^1 число единиц станет нечетным. Это и служит указанием на искажение в передаче слова. В конечном итоге все сводится к проверке соотношения (1) для символов принятого слова, что легко сделает простейшее вычислительное устройство — сумматор по модулю 2. Итак, правило приема следующее: если равенство (1) выполняется, считаем, что сообщение передано правильно, в противном случае отмечаем, что произошла ошибка и, когда это возможно, требуем повторить передачу кодового слова. Понятно, что иначе ошибки не исправить. Например, если принято «неправильное слово» 11100, то одинаково возможно, что было послано любое из кодовых слов:
01100, 10100, 11000, 11110, 11101.
Каждый из перечисленных случаев соответствует одной ошибке, а ведь ошибки могли произойти даже в трех, а то и в пяти символах.
Еще большая неприятность подстерегает нас в случае двойной ошибки или вообще четного числа ошибок. Ведь тогда соотношение (1) не нарушится, и мы воспримем искаженное слово как верное.
Описанный код, который называют кодом с общей проверкой на четность, позволяет, следовательно, обнаружить
41 любое нечетное число ошибок, но «пропускает» искажения,' если число ошибок четно.
Код с повторением и код с общей проверкой на четность — до некоторой степени антиподы. Возможности первого исправлять ошибки теоретически безграничны, но он крайне «медлителен». Второй очень быстр (всего один дополнительный символ), но зачастую «легкомыслен». В реальных каналах связи, как правило, приходится считаться с возможностью ошибок более чем в одном символе, поэтому в чистом виде код с общей проверкой на четность применяется крайне редко. Гораздо чаще применяют коды с несколькими проверочными символами (и, соответственно, с несколькими проверками на четность). Они позволяют не только обнаруживать, но и исправлять ошибки, и не только одиночные, но и кратные, и притом делать это гораздо эффективнее, чем упоминавшийся нами код с повторением. Это можно проиллюстрировать на одном красноречивом и в то же время простом примере.
Рассмотрим множество всех двоичных слов длины 9 (с их помощью можно закодировать 2®=512 сообщений). Расположим символы каждого слова ссіссг. . .а9 в квадратной таблице следующим образом:
Таблица 14
O1 CJt2 «Ї
OC4 «5
OC7 «8 «9
К каждой строке и к каждому столбцу этой таблицы добавим еще по одному (проверочному) символу с таким расчетом, чтобы в строках и столбцах получившейся таблицы (таблица 15) было четное число единиц.
При этом, например, для первой строки и первого столбца будут выполняться проверочные соотношения: ?i=ai+aa+a3 (mod 2), ?i=ai+a4+a? (mocJ 2) и аналогично для остальных строк и столбцов. Заметим, что ?i+?a+?s=?4+?6+?e (mod 2).
Обе эти суммы равны 0, если в слове сца^. . .сс9 четное число единиц, в противном случае обе они равны 1. Это дает воз-
42 ґ Таблица 15
OC1 CC2 CC3 Pl
CCi «5 ae P2
O7 CCs CC3 P3
P4 ?5 Pe P7
можность поместить в таблице 15 еще один проверочный символ ?7, равный
?,=?i+?2+?3=?4+?5+?c (mod 2).
Например, слову 011010001 отвечает следующая таблица:
Таблица 16
0 1 1 0
0 1 0 1
0 0 I J
0 0 J 0 0
Зти «маленькие хитрости» позволяют, оказывается, исправить любую одиночную ошибку, возникшую в процессе передачи, а сверх того и обнаружить любую двойную ошибку, В самом деле, если произошла одна ошибка, то нарушаются проверочные соотношения ровно для одной строки и ровно для одного столбца, как раз той строки и того столбца, на пересечении которых стоит ошибочный символ. Если же произошла двойная ошибка, то это приводит к нарушению проверок на четность либо в двух строках, либо в двух столбцах, либо сразу в двух строках и двух столбцах. По этим признакам мы и обнаруживаем двойную ошибку. (Однако исправить ее мы не можем — почему?)
Добавим к сказанному, что данный код позволяет обнаруживать многие, хотя и не все, ошибки более высокой
43 кратности (в трех, четырех и т. д. символах). Например,' обнаруживаются тройные ошибки в символах ос ос2, а3 или в символах Oti, а2, а6. А вот тройная ошибка в символах Oc1, ос2, аь не может быть обнаружена, она будет воспринята как одиночная.
