Идея кодов Рида-Соломна
Если говорить упрощенно, то основная идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного в виде полинома D, на неприводимый полином G
(т.е. такой полином, который не разлагается в произведение полиномов меньшей степени), известный обоим сторонам, в результате чего получается кодовое слово C, опять таки представленное в виде полинома.
Декодирование осуществляется с точностью до наоборот: если при делении кодового слова C на полином G, декодер внезапно получает остаток, то он может "рапортовать наверх" об ошибке. Соответственно, если кодовое слово разделилось нацело, то — его передача завершилась успешно.
Если степень полинома G (называемого так же порождающим полиномом) превосходит степень кодового слова по меньшей мере на две степени, то декодер может не только обнаруживать, но и исправлять одиночные ошибки. Если же превосходство степени порождающего полинома над кодовым словом равно четырем, то восстановлению поддается и двойные ошибки. Короче говоря, степень полинома k
связана с максимальным количеством исправляемых ошибок t следующим образом: k = 2*t. Следовательно, кодовое слово должно содержать два дополнительных символа на одну исправляемую ошибку. В то же время, максимальное количество распознаваемых ошибок равно t, т. е. избыточность составляет один символ на каждую распознаваемую ошибку.
В отличии от кодов Хемминга, коды Рида-Соломона могут исправлять любое разумное количество ошибок при вполне приемлемом уровне избыточности. Спрашиваете, за счет чего это достигается? Смотрите, в кодах Хемминга контрольные биты контролировали лишь те информационные биты, что находятся по правую сторону от них и игнорировали всех "левосторонних" товарищей". Обратимся к таблице 21.1, — добавление восьмого контрольного бита D ничуть не улучшило помехозащищенность кодирования, поскольку контрольному биту D было некого контролировать. В кодах же Рида-Соломона контрольные биты распространяют свое влияние на все информационные биты и потому, с увеличением количества контрольных бит, увеличивается и количество распознаваемых/устраняемых ошибок.
Именно благодаря последнему обстоятельству, собственно, и вызвана ошеломляющая популярность корректирующих кодов Рида-Соломона.
Теперь о грустном. Для работы с кодами Рида-Соломона обычная арифметика, увы, не подходит и вот почему. Кодирование предполагает вычисления по правилам действия над многочленами, с коэффициентами которых надо выполнять операции сложения, вычитания, умножения и деления, причем все эти действия не должны сопровождаться каким-либо округлением промежуточных результатов (даже при делении!), чтобы не вносить неопределенность. Причем, и промежуточные, и конечные результаты не имеют права выходить за пределы установленной разрядной сетки… постой! Воскликнет внимательный читатель! Да ведь это невозможно! Чтобы при умножении и не происходило "раздувания" результатов, — кто же в этот бред поверит?!
Впрочем, если как следует подумать головой, частично призвав на помощь и другие части тела, можно сообразить, что умножать информационное слово на порождающий полином вовсе и не обязательно, можно поступить гораздо хитрее:.
1. Добавляем к исходному информационному слову D
справа k нулей, в результате чего у нас получается слово длины n = m + r и полином Xr**D, где m — длина информационного слова.;
2. Делим полученный полином Xr**D на порождающий полином G и вычисляем остаток от деления R, такой что: Xr*D = G*Q + R, где Q — частное, которое мы благополучно игнорируем за ненадобностью, — сейчас нас интересует только остаток.;
3. Добавляем остаток R к информационному слову D, в результате чего получаем "симпатичное" кодовое слово C, информационные биты которогоых хранятся отдельно от контрольных бит. Собственно, тот остаток, который мы получили в результате деления — и есть корректирующие коды Рида-Соломона. Между нами говоря, способ кодирования, при котором информационные и контрольные символы хранятся раздельно называется систематическим кодированием и такое кодирование весьма удобно с точки зрения аппаратной реализации.
4. Мысленно прокручиваем пункты 1, 2 и 3 пытаясь обнаружить на какой же стадии вычислений происходит выход за разрядную сетку и… такой стадии нет! Все нормальнопучком! Остается лишь отметить, что информационное слово + плюс корректирующие коды можно записать как: T == Xr*D + R = GQ.
Декодирование полученного слова T
осуществляется точно так же, как уже и было описано ранее. Если при делении слова T (которое в действительности является произведением G на Q) на порождающий полином G образуются остаток, то слово T искажено и, соответственно, наоборот.
Теперь — вопрос на засыпку. Как вы собираетесь осуществлять деление полиномов в рамках общепринятой алгебры? В целочисленной арифметике деление определено не для всех пар чисел (вот в частности, 2 нельзя разделить на 3, а 9 нельзя разделить на 4, — без потери значимости естественно). Что же касается "плавучки", — то ее точность еще та (в смысле точность катастрофически недостаточная для эффективного использования кодов Рида-Соломона), к тому же она достаточнодовольно сложна в аппаратной реализации. Ладно, в IBM PC с процессором Pentium, быстродействующий математическийх сопроцессор всем нам дан по дефолооту, но что делать разработчикам ленточных накопителей, винчестеров, приводов CD-приводов наконец? ИспользоватьПихать в них процессор Pentium 4четвертый Пень?! Нет уж, увольте, — лучше воспользоваться специальной арифметикой, — арифметикой конечных групп, называемых полями Галуа. Достоинство этой арифметики в том, что операции сложения, вычитания, умножения и деления определены для всех членов поля (естественно, исключая ситуацию деленияе на ноль), причем, число, полученное в результате любой из этих операций, обязательно присутствует в группе! Таким образом. е. при делении любого целого числа A, принадлежащего множеству 0…255 на любое целое число B из того же множества (естественно, B не должно быть равно нулю), мы получим число C, входящее в данное множество.
А поэтому, потерь значимости не происходит и никакой неопределенности не возникает!
Таким образом, корректирующие коды Рида-Соломона основаны на полиномиальных операциях в полях Галуа и требует от программиста владения сразу несколькими аспектами высшей математики из раздела теории чисел. Как и все "высшее", придуманное математиками, поля Галуа есть суть абстракция, которую невозможно ни наглядно представить, ни "пощупать" руками. ЕеЕе просто надо просто принять как набор аксиом, не пытаясь вникнуть в его смыл, достаточно всего лишь знать, что она работает — вот и все. А еще есть полиномы "немерянных" степеней и матрицы в "пол-Европы", от которых нормального системщика извините тошнитза выражение блевать тянет (увы, программист-математик скорее исключение, чем правило).
Поэтому, прежде чем ринуться в непроходимые джунгли математического леса абстракций, давайте сконструируем макет кодера/декодера Рида-Соломона, работающий по правилам обычной целочисленной алгебры. Естественно, за счет неизбежного в этом случае расширения разрядной сетки, такому кодеру/декодеру будет очень трудно найти практическое применение, но… зато он нагляден и позволяет не только понять, но и почувствовать принцип работы корректирующих кодов Рида-Соломона.
Мы будем исходить из того, что если g = 2n + 1, то для любого a a из диапазона 0…2n, произведение a*g = c (где с — кодовое слово), будет представлять по сути полную мешанину битов обоих исходных чисел.
Допустим n = 2, тогда g = 3. Легко видеть, — на что бы мы не умножали g — хоть на 0, хоть на 1, хоть на 2, хоть на 3, полученный результат делиться нацело на g в том и только в том случае, если никакой из его битов не инвертирован (т.о е.сть, попросту говоря, одиночные ошибки — отсутствуют).
Остаток от деления однозначно указывает на позицию ошибки (при условии, что ошибка одиночная, групповые же ошибки данный алгоритм исправлять не способен).
Точнее, если ошибка произошла в позиции x, то остаток от деления k будет равен k = 2x. Для быстрого определения x по k
можно воспользоваться тривиальным табличным алгоритмом. Впрочем, для восстановления сбойного бита знать его позицию совершенно необязательно, достаточно сделать R = e ^ k, где e — искаженное кодовое слово, ^ — операция XOR (исключающее ИЛИ), а R — восстановленное кодовое слово.
В общем, законченная реализация кодера/декодера Рида-Соломона, работающего по обычной арифметике (т. е. с неоправданным расширением разрядной сетки), и исправляющим любые одиночные ошибки в одном 8-битном информационном слове (впрочем, программу легко адоптировать и под 16-байтовые информационные слова), может выглядеть так как показано в листинге 2.9. Обратите внимание, что кодер реализуется чуть ли не на порядок проще декодера. В настоящем декодере Рида-Соломна, способном исправлять групповые ошибки, этот разрыв еще значительнее. :
Листинг 21.9. [/etc/EDC.ECC/rs.simplest.c] Простейший пример реализации кодера/декодера Рида-Соломона, работающего по обычной арифметике (т.е. с неоправданным расширением разрядной сетки), и исправляющим любые одиночные ошибки в одном 8-битном информационном слове (впрочем, программу легко адоптировать и под 16-байтовые информационные слова). Обратите внимание, что кодер реализуется чуть ли не на порядок проще декодера. В настоящем декодере Рида-Соломна, способном исправлять групповые ошибки, этот разрыв еще значительнее.
/*----------------------------------------------------------------------------
*
* ПРОСТЕЙШИЙ КОДЕР/ДЕКОДЕР РИДА-СОЛОМОНА
* ======================================
*
* Build 0x001 @ 02.07.2003
----------------------------------------------------------------------------*/
// ВНИМАНИЕ! данный кодер/декодер построен на основе обычной арифметики,
// _не_ арифметики полей Галуа, в результате чего его практические возможности
// более чем ограничены, тем не менее он нагляден и удобен для изучения
#include <stdio.h>
#define SYM_WIDE 8 // ширина входного информационного символа (бит)
#define DATAIN 0x69 // входные данные (один байт)
#define ERR_POS 3 // номер бита, который будет разрушен сбоем
// неприводимый полином
#define MAG (1<<(SYM_WIDE*1) + 1<<(SYM_WIDE*0))
// -------------------------------------------------------------------------------
// определение позиции ошибки x по остатку k от деления кодового слова на полином
// k = 2^x, где "^" – возведение в степень
// функция принимает k и возвращает x
// -------------------------------------------------------------------------------
int pow_table[9] = {1,2,4,8,16,32,64,128,256};
lockup(int x) {int a;for(a=0;a<9;a++) if(pow_table[a]==x)return a; return -1;}
main()
{
int i; int g; int c; int e; int k;
fprintf(stderr,"simplest Reed-Solomon endoder/decoder by Kris Kaspersky\n\n");
i = DATAIN; // входные данные (информационное слово)
g = MAG; // неприводимый полином
printf("i = %08x (DATAIN)\ng = %08x (POLYNOM)\n", i, g);
// КОДЕР РИДА-СОЛОМОНА (простейший, но все-таки кое-как работающий)
// вычисляем кодовое слово, предназначенное для передачи
c = i * g; printf("c = %08x (CODEWORD)\n", c);
// конец КОДЕРА
// передаем с искажениями
e = c ^ (1<<ERR_POS); printf("e = %08x (RAW RECIVED DATA+ERR)\n\n", e);
/* ^^^^ искажаем один бит, имитируя ошибку передачи */
// ДЕКОДЕР РИДА-СОЛОМОНА
// проверяем на наличие ошибок передачи
// (фактически это простейший декодер Рида-Соломона)
if (e % g)
{
// ошибки обнаружены, пытаемся исправить
printf("RS decoder says: (%x) error detected\n{\n", e % g);
k = (e % g); // k = 2^x, где x - позиция сбойного бита
printf("\t0 to 1 err position: %x\n", lockup(k));
printf ("\trestored codeword is: %x\n}\n", (e ^= k));
}
printf("RECEIVED DATA IS: %x\n", e / g);
// КОНЕЦ ДЕКОДЕРА
}
Результат работы простейшего кодера/декодера Рида-Соломона показан в листинге 2.10. Обратите внимание — искаженный бит удалось успешно исправить, однако, для этого к исходному информационному слову пришлось добавить не два, а целых три бита (если вы возьмете в качестве входного слова максимально допустимое восьмибитное значение 0xFF, то кодовое слово будет равно 0x1FE00, а так как 210 = 1024, то свободных разрядов уже не хватает и приходится увеличивать разрядную сетку до 211, в то время как младшие биты кодового слова фактически остаются незадействованными и "правильный" кодер должен их "закольцевать", грубо говоря замкнув обрабатываемые разряды на манер кольца.
Листинг 21.10. Результат работы простейшего кодера/декодера Рида-Соломона работы простейшего кодера/декодера Рида-Соломона. Обратите внимание — искаженный бит удалось успешно исправить, однако, для этого к исходному информационному слову пришлось добавить не два, а целых три бита (если вы возьмете в качестве входного слова максимально допустимое восьми битное значение 0xFF, то кодовое слово будет равно 0x1FE00, а так как 210 = 10000, то свободных разряднов уже не хватает и приходится увеличивать разрядную сетку до 211, в то время как младшие биты кодового слова фактически остаются незадействованными и "правильный" кодер должен их "закольцевать", грубо говоря замкнув обрабатываемые разряды на манер кольца.
i = 00000069 (DATAIN)
g = 00000200 (POLYNOM)
c = 0000d200 (CODEWORD)
e = 0000d208 (RAW RECIVED DATA+ERR)
RS decoder says: (8) error detected
{
0 to 1 err position: 3
restored codeword is: d200
}
RECEIVED DATA IS: 69
