Корректирующие коды и помехоустойчивое кодирование (азы)
Персональные компьютеры с их битами и байтами настолько прочно вошли в нашу жизнь, что программисты вообще перестали задумываться о теории кодирования информации, принимая ее как должное. Между тем, здесь все не так просто, как может показаться на первый взгляд.
Фактически, кодирование есть ни что иное, как преобразование сообщения в последовательность кодовых символов так же называемых кодовыми словами. Любое дискретное сообщение состоит из конечного числа элементов: в частности, текст состоит из букв, изображение состоит из пикселей, машинная программа состоит из команд и т. д., — все они образуют алфавит источника сообщения. При кодировании происходит преобразование элементов сообщения в соответствующие им числа — кодовые символы, причем каждому элементу сообщения присваивается уникальная совокупность кодовых символов, называемая кодовой комбинацией. Совокупность кодовых комбинаций, образующих сообщение, и есть код. Множество возможных кодовых символов называется кодовым алфавитом, а их количество (далее по тексту обозначаемое малой латинской m) — основанием кода.
Впрочем, все это вы уже наверняка знаете (а если не знаете, — то без труда найдете исчерпывающее объяснение основ кодирования в любом учебнике по информатике), но знаете ли вы, что такое расстояние Хемминга? Это — минимальное количество различий между двумя различными допустимыми кодовыми словами
и в теории помехоустойчивого кодирования расстояние Хемминга играет основополагающую роль. Рассмотрим, например, следующий четырех битный код (листинг 21.1).:
Листинг 21.1. Пример простейшего четырех битного кода с расстоянием Хемминга, равныом единице.
0 à 0000; 4 à 0100; 8 à 1000; 12 à 1100;
1 à 0001; 5 à 0101; 9 à 1001; 13 à 1101;
2 à 0010; 6 à 0110; 10 à 1010; 14 à 1110;
3 à 0011; 7 à 0111; 11 à 1011; 15 à 1111;
Такой код широко используется в вычислительной технике, несмотря на его невозможность обнаружить ошибки.
Это обыкновенный двоичный код, который можно встретить в некоторых "однокристалках", вмещающий в свои 4 бита 16 символов (т. е. с его помощью можно закодировать 16 букв алфавита). Как нетрудно убедиться, что два любых символа этого кода отличаются, по меньшей мере, на один бит, следовательно, расстояние Хемминга для такого кода равно единице (что условно обозначает как
d = 1).
А вот другой четырех битный код с расстоянием Хемминга, равным двум, способный обнаруживать одиночные ошибки (листинг 21.2).:
Листинг 21.2. Пример четырех битного кода с расстоянием Хемминга, равныом двум, способный обнаруживать одиночные ошибки.
0 à 0000; 4 à 1001;
1 à 0011; 5 à 1010;
2 à 0101; 6 à 1100;
3 à 0110; 7 à 1111;
На этот раз, два произвольных символа отличаются как минимум в двух позициях, за счет чего информационная емкость такого кода сократилась с 16- до 8 символов. Постойте-постойте! — воскликнет иной читатель. — Что это за бред? Куда девалась комбинация 0001 или 0010 например? Нет, это не бред и указанных комбинаций бит в данном коде действительно нет, точнее они есть, но объявлены запрещенными. Благодаря этому обстоятельству наш подопечный код способен обнаруживать любые одиночные ошибки. Возьмем, например, символ "1010" и исказим в нем произвольный бит (но только один!). Пусть это будет второй слева бит, — тогда искаженный символ станет выглядеть так: "1110". Поскольку, комбинация "1110" является запрещенной, декодер может засвидетельствовать наличие ошибки. Увы, только засвидетельствовать, но не исправить, т. к. для исправления даже одного-единственного сбойного байта требуются увеличить расстояние Хемминга как минимум до трех. Поскольку, 4-?битный код с d = 3 способен вмещать в себя лишь два различных символа, то он крайне ненагляден, и потому нам лучше выбрать код с большей разрядностью.
Хорошо, пусть это будет 10-битный код с d = 5 (листинг 21.3).
Листинг 21.3. Пример 10-битного кода, с расстоянием Хемминга равныом пяти, способного обнаруживать четырех битные ошибки, а исправлять — двух битовыедвух битовые.
0000000000 0000011111 1111100000 1111111111
Возьмем, к примерупримеру, символ "0000011111" и изменимискорежим два его любых бита, получив в итоге что-то наподобие: "0100110111". Поскольку, такая комбинация является запрещенной, декодер понимает, что произошла ошибка. Достаточно очевидно, что если количество сбойных бит меньше расстояния Хемминга хотя бы наполовину, то декодер может гарантированно восстановить исходный символ. Действительно, если между двумя любыми разрешенными символами существует не менее пяти различий, то искажение двух бит всякого такого символа приведет к образованию нового символа (обозначим его k), причем расстояние Хемминга между k и оригинальным символом равно числу непосредственно искаженных бит (т. е. в нашем случае двум), а расстояние до ближайшего соседнего символа равно: d – k (т. е. в нашем случае трем). Другими словами, пока d – k > k
декодер может гарантированно восстановить искаженный символ. В тех случаях, когда d > k > d – k, успешное восстановление уже не гарантируется, но при удачном стечении обстоятельств все-таки оказывается в принципе возможным.
Возвращаясь к нашему символу "0000011111," давайте на этот раз исказим не два бита, а четыре: "0100110101" и попробуем его восстановить. Изобразим процесс восстановления графически (листинг 21.4).:
Листинг 21.4. Восстановление четырех битной ошибки
0000000000 0000011111 1111100000 1111111111
0100110101 0100110101 0100110101 0100110101
---------- ---------- ---------- ----------
5 отличий 4 отличия 6 отличий 5 отличий
Грубо говоря, обнаружив ошибку, декодер последовательно сличает искаженный символ со всеми разрешенными символами алфавита, стремясь найти символ наиболее "похожий" на искаженный. Точнее — символ с наименьшим числом различий, а еще точнее — символ, отличающийся от искаженного не более чем в (d – 1) позициях. Легко увидеть, что в данном случае нам повезло и восстановленный символ совпал с истинным. Однако, если бы четыре искаженных бита распределились бы так: "0111111111", то декодер принял бы этот символ за "1111111111" и восстановление оказалось бы неверным.
Таким образом, исправляющая способность кода определяется по следующей формуле: для обнаружения r ошибок расстояние Хемминга должно быть больше или равно r, а для коррекции r ошибок, расстояние Хемминга должно быть, по крайней мере, на единицу больше удвоенного количества r (листинг 21.5).
Листинг 21.5. Корректирующие способности простого кода Хемминга
обнаружение ошибок: d
>= r
исправление ошибок: d
> 2r
информационная емкость: 2n/d
Теоретически количество обнаруживаемых ошибок неограниченно, практически же информационная емкость кодовых слов стремительно тает с ростом d. Допустим, у нас есть 24 байта данных, и мы хотели бы исправлять до двух ошибок на каждый такой блок. Тогда нам придется добавить к этому блоку еще 49 байт, в результате чего реальная информационная емкость блока сократиться всего… до 30%! Хорошенькая перспективаперспектива, не так ли? Столь плачевный результат объясняется тем, что биты кодового слова изолированы друг от друга и изменение одного из них никак не сказывается на окружающих. А что если…
Пусть все биты, номера которых есть степень двойки, станут играть роль контрольных битов, а оставшиеся и будут обычными ("информационными") битами сообщения. Каждый контрольный бит должен отвечать за четность суммы (т. е.
если сумма проверяемых бит — четна, то контрольный бит будет равен нулю и, соответственно, наоборот) некоторой, принадлежащей ему группы битов, причем один и тот же информационный бит может относиться к различным группам. Тогда, один информационный бит сможет влияет на несколько контрольных и потому информационная емкость слова значительно (можно даже сказать чудовищно) возрастет. Остается только выбрать наиболее оптимальное разделение сфер влияния.
Согласно методу помехозащитного кодирования, предложенного Хеммингом, для того, чтобы определить какие контрольные биты контролируют информационный бит, стоящий в позиции k, мы должны разложить k
по степеням двойки, как это показано в таблице 21.1.:
Таблица 21.1. Разделение бит на контрольные и информационные
|
Позиция |
Какими битами контролируется |
|
|
1 (A) |
20 = 1 |
Это контрольный бит, никто его не контролирует |
|
2 (B) |
21 = 2 |
Это контрольный бит, никто его не контролирует |
|
3 |
20+21 = 1 + 2 = 3 |
Контролируется 1 и 2 контрольными битами |
|
4 (C) |
22 = 4 |
Это контрольный бит, никто его не контролирует |
|
5 |
20+22 = 1 + 4 = 5 |
Контролируется 1 и 4 контрольными битами |
|
6 |
21+22 = 2 + 4 = 6 |
Контролируется 2 и 4 контрольными битами |
|
7 |
20+21+22 = 1 + 2 + 4 = 7 |
Контролируется 1, 2 и 4 контрольными битами |
|
8 (D) |
23 = 8 |
Это контрольный бит, никто его не контролирует |
q Бит A, контролирующий биты 3, 5 и 7 равен нулю, т. к. их сумма (0 + 1 + 1) четна.
q Бит B, контролирующий биты 3, 6 и 7 равен единицеодному, т. к.
их сумма (0 + 0 + 1) нечетна.
q Бит C, контролирующий биты 5, 6 и 7 равен нулю, т. к. их сумма (1 + 0 + 1) четна.
Таким образом, "новоиспеченное" кодовое слово будет выглядеть так: "0100101", где жирным шрифтом выделены контрольные биты (листинг 21.6).
Листинг 21.6. Кодовое слово вместе с информационными битами
AB0C101
1234567
Допустим, при передаче наше слово было искажено в одной позиции и стало выглядеть так: 0100111. Сможем ли мы обнаружить такую ошибку? А вот сейчас и проверим! Так, бит A должен быть равен: (0 + 1 + 1) % 2 = 0, что соответствует истине. Бит B должен быть равен (0 + 1 + 1) % 2 = 0, а в нашем слове он равен единице. Запомним номер "неправильного" контрольного бита и продолжим. Бит C должен быть равен (1 + 1 + 1) % 2 = 1, а он равен нулю! Ага, значит, контрольные биты в позициях 2 (бит B) и 4 (бит C) обнаруживают расхождение с действительностью. Их сумма (2 + 4 = 6) и дает позицию сбойного бита. Действительно, в данном случае номер искаженного бита будет равен 6, — инвертируем его, тем самым, восстанавливая наше кодовое слово в исходный вид.
А что, если искажение затронет не информационный, а контрольный бит? Проверка показывает, что позиция ошибки успешно обнаруживается и в этом случае и контрольный бит при желании может быть легко восстановлен по методике уже описанной выше (только если ли в этом смысл? ведь контрольные биты все равно выкусываются в процессе декодирования кодового слова).
На первый взгляд кажется, что коды Хемминга жутко неэффективны, ведь на 4 информационных бита у нас приходится 3 контрольных, однако, поскольку номера контрольных бит представляют собой степень двойки, то с ростом разрядности кодового слова они начинают располагаться все реже и реже.
Так, ближайший к биту C контрольный бит D находится в позиции 8 (т . е. в "трех шагах"), зато контрольный бит E отделен от бита D уже на 24 – 23 – 1 = 7 "шагов", а контрольный бит F и вовсе — на – 25 – 24 – 1 = 15 "шагов".
Таким образом, с увеличением разрядности обрабатываемого блока, эффективность кодов Хемминга стремительно нарастает, что и показывает следующая программа (листинг 21.7) и результаты расчетов, выполненные с ее помощью (листинг 21.8).:
Листинг 21.7. Расчет эффективной информационной емкости кодов Хемминга для слов различной длины
main()
{
int a;
int _pow = 1;
int old_pow = 1;
int N, old_N = 1;
printf( "* * * hamming code efficiency test * * * by Kris Kaspersky\n"\
" BLOCK_SIZE FUEL UP EFFICIENCY\n"\
"-----------------------------------\n");
for (a = 0; a < MAX_POW; a++)
{
N = _pow - old_pow - 1 + old_N;
printf("%8d %8d %8.1f%%\n",_pow, N, (float) N/_pow*100);
// NEXT
old_pow = _pow; _pow = _pow * 2; old_N = N;
} printf("-----------------------------------\n");
}
Листинг 21.888. Результат расчета эффективной информационной емкости кодов Хемминга для слов различной длины
BLOCK_SIZE FUEL UP EFFICIENCY
-----------------------------------
1 0 0.0%
2 0 0.0%
4 1 25.0%
8 4 50.0%
16 11 68.8%
32 26 81.3%
64 57 89.1%
128 120 93.8%
256 247 96.5%
512 502 98.0%
1024 1013 98.9%
2048 2036 99.4%
4096 4083 99.7%
8192 8178 99.8%
16384 16369 99.9%
32768 32752 100.0%
65536 65519 100.0%
131072 131054 100.0%
262144 262125 100.0%
524288 524268 100.0%
-----------------------------------
Из приведенной выше распечатки (см. листинг 21.8) видно, что при обработке блоков, "дотягивающихся" хотя бы до 1024 бит, накладными расходами на контрольные биты можно полностью пренебречь.
К сожалению, коды Хемминга способны исправлять лишь одиночные ошибки, т. е. допускают искажение всего лишь одного сбойного бита на весь обрабатываемый блок. Естественно, с ростом размеров обрабатываемых блоков увеличивается и вероятность ошибок. Поэтому, выбор оптимальной длины кодового слова является весьма нетривиальной задачей, как минимум требующей знания характера и частоты возникновения ошибок используемых каналов передачи информации. В частности, для ленточных накопителей, лазерных дисков, винчестеров и тому подобных устройств, коды Хемминга оказываются чрезвычайно неэффективными. Зачем же тогда мы их рассматривали? А затем, что понять прогрессивные системы кодирования (к которым в том числе относятся и коды Рида-Соломона), ринувшись атаковать их "с нуля", практически невозможно, ибо они завязаны на сложной, действительно высшей математике, но ведь не Боги горшки обжигают, верно?
