Техника защиты компакт-дисков от копирования

Идея кодов Рида-Соломна


Если говорить упрощенно, то основная идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного в виде полинома 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


Содержание раздела