Глава 3. Количественная оценка информации 11 страница

Число возможных циклических (n, k)-кодов значительно меньше числа различных групповых (n, k)-кодов.

При описании циклических кодов n-разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной х. Показатели степени у x соответствуют номерам разрядов (начиная с нулевого), а коэффициентами при x в общем случае являются элементы поля GF(q). При этом наименьшему разряду числа соответствует фиктивная переменная х° = 1. Многочлен с коэффициентами из поля GF(q) называют многочленом над полем GF(q). Так как мы ограничиваемся рассмотрением только двоичных кодов, то коэффициентами при x будут только цифры 0 и 1. Иначе говоря, будем оперировать с многочленами над полем GF(2).

Запишем, например, в виде многочлена образующую кодовую комбинацию 01011:

Поскольку члены с нулевыми коэффициентами при записи многочлена опускаются, образующий многочлен·

Наибольшую степень x в слагаемом с ненулевым коэффициентом называют степенью многочлена. Теперь действия над кодовыми комбинациями сводятся к действиям над многочленами. Суммирование многочленов осуществляется с приведением коэффициентов по модулю два.

Указанный циклический сдвиг некоторого образующего многочлена степени n- — k без переноса единицы в конец кодовой комбинации соответствует простому умножению на x. Умножив, например, первую строку матрицы (001011), соответствующую многочлену go(x) = х^3+x+1, на х, получим вторую строку матрицы (010110), соответствующую многочлену x · g0(x).

 

Нетрудно убедиться, что кодовая комбинация, получающаяся при сложении этих двух комбинаций, также будет соответствовать результату умножения многочлена на многочлен x+1.

Циклический сдвиг строки матрицы с единицей в старшем (n-m) разряде (слева) равносилен умножению соответствующего строке многочлена на x с одновременным вычитанием из результата многочлена хⁿ⁺¹ = х^n-1, т. е. с приведением по модулю хⁿ⁺¹.

Отсюда ясно, что любая разрешенная кодовая комбинация циклического кода может быть получена в результате умножения образующего многочлена на некоторый другой многочлен с приведением результата по модулю хⁿ⁺¹. Иными словами, при соответствующем выборе образующего многочлена любой многочлен циклического кода будет делиться на него без остатка.

Ни один многочлен, соответствующий запрещенной кодовой комбинации, на образующий многочлен без остатка не делится. Это свойство позволяет обнаружить ошибку. По виду остатка можно определить и вектор ошибки.

Умножение и деление многочленов весьма просто осуществляется на регистрах сдвига с обратными связями, что и явилось причиной широкого применения циклических кодов.

Математическое введение к циклическим кодам. Так как каждая разрешенная комбинация n-разрядного циклического кода есть произведение двух многочленов, один из которых является образующим, то эти комбинации можно рассматривать как подмножества всех произведений многочленов степени не выше n—1. Это наталкивает на мысль использовать для построения этих кодов еще одну ветвь теории алгебраических систем, а именно — теорию колец.

Как следует из приведенного ранее определения (см. § 6.3), для образования кольца на множестве n-разрядных кодовых комбинаций необходимо задать две операции: сложение и умножение.

Операция сложения многочленов уже выбрана нами с приведением коэффициентов по модулю два.

Определим теперь операцию умножения. Нетрудно видеть, что операция умножения многочленов по обычным правилам с приведением подобных членов по модулю два может привести к нарушению условия замкнутости. Действительно, в результате умножения могут быть получены многочлены более высокой степени, чем n — 1, вплоть до 2(n— 1), а соответствующие им кодовые комбинации будут иметь число разрядов, превышающее n и, следовательно, не относятся к рассматриваемому множеству. Поэтому операция символического умножения задается так:

1) многочлены перемножаются по обычным правилам, но с приведением подобных членов по модулю два;

2) если старшая степень произведения не превышает n— 1, то оно и является результатом символического умножения;

3) если старшая степень произведения больше или равна n, то многочлен произведения делится на заранее определенный многочлен степени n и результатом символического умножения считается остаток от деления.

Степень остатка не превышает n — 1, и, следовательно, этот многочлен принадлежит к рассматриваемому множеству n-разрядных кодовых комбинаций.

При анализе циклического сдвига с перенесением единицы в конец кодовой комбинации установлено, что таким многочленом n-й степени является многочлен хⁿ⁺¹.

Действительно, в результате умножения многочлена степени n-1 на x получим:

Следовательно, чтобы результат умножения и теперь соответствовал кодовой комбинации, образующейся путем циклического сдвига исходной кодовой комбинации, в нем необходимо заменить хⁿ на 1. Такая замена эквивалентна делению полученного при умножении многочлена на xⁿ⁺¹ с записью в качестве результата остатка от деления, что обычно называют взятием остатка или приведением по модулю хⁿ⁺¹ (сам остаток при этом называют вычетом).

Выделим теперь в нашем кольце подмножество всех многочленов, кратных некоторому многочлену g(x). Такое подмножество называют идеалом, а многочлен g(x) — порождающим многочленом идеала.

Количество различных элементов в идеале определяется видом его порождающего многочлена. Если на порождающий многочлен взять 0, то весь идеал будет составлять только этот многочлен, так как умножение его на любой другой многочлен дает 0.

Если за порождающий многочлен принять l[g(x) = 1], то в идеал войдут все многочлены кольца. В общем случае число элементов идеала, порожденного простым многочленом степени n — k, составляет 2^k.

Теперь становится понятным, что циклический двоичный код в построенном нами кольце n-разрядных двоичных кодовых комбинаций является идеалом.

Остается выяснить, как выбрать многочлен g(x), способный породить циклический код с заданными свойствами.

Требования, предъявляемые к образующему многочлену. Согласно определению циклического кода все многочлены, соответствующие его кодовым комбинациям, должны делиться на g(x) без остатка. Для этого достаточно, чтобы на g(x) делились без остатка многочлены, составляющие образующую матрицу кода. Последние получаются циклическим сдвигом, что соответствует последовательному умножению g(x) на x с приведением по модулю хⁿ⁺¹.

Следовательно, в общем случае многочлен g_i(x) является остатком от деления произведения g(x) ·xⁱ на многочлен хⁿ⁺¹ и может быть записан так:

где с = 1, если степень g(x)xⁱ превышает n — 1; с = 0, если степень g(x)xⁱ не превышает n—1.

Отсюда следует, что все многочлены матрицы, а поэтому и все многочлены кода будут делиться на g(x) без остатка только в том случае, если на g(x) будет делиться без остатка многочлен хⁿ⁺¹.

Таким образом, чтобы g(x) мог породить идеал, а следовательно, и циклический код, он должен быть делителем многочлена хⁿ⁺¹.

Поскольку для кольца справедливы все свойства группы, а для идеала — все свойства подгруппы, кольцо можно разложить на смежные классы, называемые в этом случае классами вычетов по идеалу.

Первую строку разложения образует идеал, причем нулевой элемент располагается крайним слева. В качестве образующего первого класса вычетов можно выбрать любой многочлен, не принадлежащий идеалу. Остальные элементы данного класса вычетов образуются путем суммирования образующего многочлена с каждым многочленом идеала.

Если многочлен g(x) степени m = n — k является делителем хⁿ⁺¹, то любой элемент кольца либо делится на g(x) без остатка (тогда он является элементом идеала), либо в результате деления появляется остаток r(х), представляющий собой многочлен степени не выше m-1.

Элементы кольца, дающие в остатке один и тот же многочлен г_i(х), относятся к одному классу вычетов. Приняв многочлены г(х) за образующие элементы классов вычетов, разложение кольца по идеалу с образующим многочленом g(x) степени m можно представить табл. 6.10, где f(x) — произвольный многочлен степени не выше n — m — 1.

Таблица 6.10

Как отмечалось, групповой код способен исправить столько разновидностей ошибок, сколько различных классов насчитывается в приведенном разложении. Следовательно, корректирующая способность циклического кода будет тем выше, чем больше остатков может быть образовано при делении многочлена, соответствующего искаженной кодовой комбинации, на образующий многочлен кода.

Наибольшее число остатков, равное 2^m-1 (исключая нулевой), может обеспечить только неприводимый (простой) многочлен, который делится сам на себя и не делится ни на какой другой многочлен (кроме 1).

 

§ 6.7. ВЫБОР ОБРАЗУЮЩЕГО МНОГОЧЛЕНА ПО ЗАДАННОМУ ОБЪЕМУ КОДА И ЗАДАННОЙ КОРРЕКТИРУЮЩЕЙ СПОСОБНОСТИ

 

По заданному объему кода однозначно определяется число информационных разрядов k. Далее необходимо найти наименьшее n, обеспечивающее обнаружение или исправление ошибок заданной кратности. В случае циклического кода эта проблема сводится к нахождению нужного многочлена g(x).

Начнем рассмотрение с простейшего циклического кода, обнаруживающего все одиночные ошибки.

Обнаружение одиночных ошибок. Любая принятая по каналу связи кодовая комбинация h(x), возможно содержащая ошибку, может быть представлена в виде суммы по модулю два неискаженной комбинации кода f(x) и вектора ошибки ξ(x):

При делении h(x) на образующий многочлен g(x) остаток, указывающий на наличие ошибки, обнаруживается только в том случае, если многочлен, соответствующий вектору ошибки, не делится на g(x): f(x) — неискаженная комбинация кода и, следовательно, на g(x) делится без остатка.

Вектор одиночной ошибки имеет единицу в искаженном разряде и нули во всех остальных разрядах. Ему соответствует многочлен ξ(x) = хⁱ· Последний не должен делиться на g(x). Среди неприводимых многочленов, входящих в разложении хⁿ⁺¹, многочленом наименьшей степени, удовлетворяющим указанному условию, является x+1. Остаток от деления любого многочлена на x+1 представляет собой многочлен нулевой степени и может принимать только два значения: 0 или 1. Все кольцо в данном случае состоит из идеала, содержащего многочлены с четным числом членов, и одного класса вычетов, соответствующего единственному остатку, равному 1. Таким образом, при любом числе информационных разрядов необходим только один проверочный разряд. Значение символа этого разряда как раз и обеспечивает четность числа единиц в любой разрешенной кодовой комбинации, а следовательно, и делимость ее на х+1.

Полученный циклический код с проверкой на четность способен обнаруживать не только одиночные ошибки в отдельных разрядах, но и ошибки в любом нечетном числе разрядов.

Исправление одиночных или обнаружение двойных ошибок. Прежде чем исправить одиночную ошибку в принятой комбинации из n разрядов, необходимо определить, какой из разрядов был искажен. Это можно сделать только в том случае, если каждой одиночной ошибке в определенном разряде соответствуют свой класс вычетов и свой опознаватель. Так как в циклическом коде опознавателями ошибок являются остатки от деления многочленов ошибок на образующий многочлен кода g(x), то g(x) должно обеспечить требуемое число различных остатков при делении векторов ошибок с единицей в искаженном разряде. Как отмечалось, наибольшее число остатков дает неприводимый многочлен. При степени многочлена m = n — k он может дать 2^n-k-1 ненулевых остатков (нулевой остаток является опознавателем безошибочной передачи).

Следовательно, необходимым условием исправления любой одиночной ошибки является выполнение неравенства

где С_n — общее число разновидностей одиночных ошибок в кодовой комбинации из n символов; отсюда находим степень образующего многочлена кода

и общее число символов в кодовой комбинации. Наибольшие значения k и n для различных m можно найти, пользуясь табл. 6.11.

Как указывалось, образующий многочлен g(x) должен быть делителем двучлена хⁿ⁺¹. Доказано [20], что любой двучлен типа может быть представлен произведением всех неприводимых многочленов, степени которых являются делителями числа m (от 1 до m включительно). Следовательно, для любого m существует по крайней мере один неприводимый многочлен степени m, входящий сомножителем в разложение двучлена хⁿ⁺¹.

Таблица 6.11

Пользуясь этим свойством, а также имеющимися в ряде книг [20] таблицами многочленов, неприводимых при двоичных коэффициентах, выбрать образующий многочлен при известных n и m несложно. Определив образующий многочлен, необходимо убедиться в том, что он обеспечивает заданное число остатков.

Пример 6.13. Выберем образующий многочлен для случая n = 15 и m = 4.

Двучлен x¹⁵+1 можно записать в виде произведения всех неприводимых многочленов, степени которых являются делителями числа 4. Последнее делится на 1, 2, 4.

В таблице неприводимых многочленов находим один многочлен первой степени, а именно х+1, один многочлен второй степени х² + х+1 и три многочлена четвертой степени: х⁴ + x + 1, х⁴ + х³+1, х⁴ + х³+х + 1. Перемножив все многочлены, убедимся в справедливости соотношения (х+1)(х² + х + 1)(х⁴ + х+1)(х⁴ + х³+ l)(x⁴ + x³ + +x²+x+1) = x¹²+1.

Один из сомножителей четвертой степени может быть принят за образующий многочлен кода. Возьмем, например, многочлен х⁴ + х³ + 1, или в виде двоичной последовательности 11001.

Чтобы убедиться, что каждому вектору ошибки соответствует отличный от других остаток, необходимо поделить каждый из этих векторов на 11001.

Векторы ошибок т младших разрядов имеют вид:

00...0001, 00...0010, 00...0100, 00...1000.

Степени соответствующих им многочленов меньше степени образующего многочлена g(x). Поэтому они сами являются остатками при нулевой целой части. Остаток, соответствующий вектору ошибки в следующем старшем разряде, получаем при делении 00...10000 на 11001, т.е.

Аналогично могут быть найдены и остальные остатки. Однако их можно получить проще, деля на g(x) комбинацию в виде единицы с рядом нулей и выписывая все промежуточные остатки:

При последующем делении остатки повторяются.

Таким образом, мы убедились в том, что число различных остатков при выбранном g(x) равно n = 15, и, следовательно, код, образованный таким g(x), способен исправить любую одиночную ошибку С тем же успехом за образующий многочлен кода мог быть принят и многочлен х⁴+x+1. При этом был бы получен код, эквивалентный выбранному.

Однако использовать для тех же целей многочлен x⁴ + х³ + х² + x + 1 нельзя. При проверке числа различных остатков обнаруживается, что их у него не 15, а только 5 Действительно,

Это объясняется тем, что многочлен x⁴ + х³ + х² + x + 1 входит в разложение не только двучлена x¹⁵ + 1, но и двучлена х⁵ + 1.

Из приведенного примера следует, что в качестве образующего следует выбирать такой неприводимый многочлен g(x) (или произведение таких многочленов), который, являясь делителем двучлена хⁿ⁺¹, не входит в разложение ни одного двучлена типа x^ λ+1, степень которого λ меньше n. В этом случае говорят, что многочлен q(x) принадлежит показателю степени n.

В табл. 6.12 приведены основные характеристики некоторых кодов, способных исправлять одиночные ошибки или обнаруживать все одиночные и двойные ошибки.

Таблица 6.12

Это циклические коды Хэмминга для исправления одной ошибки, в которых в отличие от групповых кодов Хэмминга все проверочные разряды размещаются в конце кодовой комбинации.

Эти коды могут быть использованы для обнаружения любых двойных ошибок. Многочлен, соответствующий вектору двойной ошибки, имеет вид ξ(χ) = xⁱ + xⁱ, или ξ(x) = xⁱ(x^j-i + 1) при j>i. Так как j-i<n а g(x) не кратен x и принадлежит показателю степени n, то ξ(x) не делится на g(x), что и позволяет обнаружить двойные ошибки.

Обнаружение ошибок кратности три и ниже. Образующие многочлены кодов, способных обнаруживать одиночные, двойные и тройные ошибки, можно определить, базируясь на следующем указании Хэмминга. Если известен образующий многочлен p(x^m) кода длины n, позволяющего обнаруживать ошибки некоторой кратности z то образующий многочлен g(x) кода, способного обнаруживать ошибки следующей кратности (z+1), может быть получен умножением многочлена р(х^m) на многочлен x+1, что соответствует введению дополнительной проверки на четность. При этом число символов в комбинациях кода за счет добавления еще одного проверочного символа увеличивается до n + 1.

В табл. 6.13 приведены основные характеристики некоторых кодов, способных обнаруживать ошибки кратности три и менее.

Таблица 6.13

Обнаружение и исправление независимых ошибок произвольной кратности. Важнейшим классом кодов, используемых в каналах, где ошибки в последовательностях символов возникают независимо, являются коды Боуза — Чоудхури — Хоквингема. Доказано, что для любых целых положительных чисел m и s<n/2 существует двоичный код этого класса длины n = 2^m—1 с числом проверочных символов не более ms, который способен обнаруживать ошибки кратности 2s или исправлять ошибки кратности s. Для понимания теоретических аспектов этих кодов необходимо ознакомиться с рядом новых понятий высшей алгебры. Вопросы их построения и технической реализации рассмотрены в § 6.9. — Обнаружение и исправление пачек ошибок. Для произвольного линейного блокового (n, k)-кода, рассчитанного на исправление пакетов ошибок длины b или менее, основным соотношением, устанавливающим связь корректирующей способности с числом избыточных символов, является граница Рейджера:

При исправлении линейным кодом пакетов длины b или менее с одновременным обнаружением пакетов длины l>=b или менее требуется по крайней мере b + l проверочных символов.

Из циклических кодов, предназначенных для исправления пакетов ошибок, широко известны коды Бартона, Файра и Рида — Соломона.

Первые две разновидности кодов служат для исправления одного пакета ошибок в блоке. Коды Рида — Соломона способны исправлять несколько пачек ошибок.

Особенности декодирования циклических кодов, исправляющих пакеты ошибок, рассмотрены далее на примере кодов Файра.

Методы образования циклического кода. Существует несколько различных способов кодирования. Принципиально наиболее просто комбинации циклического кода можно получить, умножая многочлены а(х), соответствующие комбинациям безызбыточного кода (информационным символам), на образующий многочлен кода g(x). Такой способ легко реализуется. Однако он имеет тот существенный недостаток, что получающиеся в результате умножения комбинации кода не содержат информационные символы в явном виде. После исправления ошибок такие комбинации для выделения информационных символов приходится делить на образующий многочлен кода.

Применительно к циклическим кодам принято (хотя это и не обязательно) отводить под информационные k символов, соответствующих старшим степеням многочлена кода, а под проверочные n — k символов низших разрядов.

Чтобы получить такой систематический код, применяется следующая процедура кодирования.

Многочлен а(х), соответствующий k-разрядной комбинации безызбыточного кода, умножаем на х^m, где m = n — k. Степень каждого одночлена, входящего в а(х), увеличивается, что по отношению к комбинации кода означает необходимость приписать со стороны младших разрядов m нулей. Произведение а(х)х^m делим на образующий многочлен g(x). В общем случае при этом получаем некоторое частное q(x) той же степени, что и а(х) и остаток r(х). Последний прибавляем к а(х)х^m. В результате получаем многочлен

Поскольку степень g(x) выбираем равной m, степень остатка r(х) не превышает m — 1. В комбинации, соответствующей многочлену а(х)х^m, m младших разрядов нулевые, и, следовательно, указанная операция сложения равносильна приписыванию r(х) к а(х) со стороны младших разрядов.

Покажем, что f(x) делится на g(x) без остатка, т. е. является многочленом, соответствующим комбинации кода. Действительно, запишем многочлен а(х)х^m в виде

Так как операции сложения и вычитания по модулю два идентичны, r(х) можно перенести влево, тогда

что и требовалось доказать.

Таким образом, циклический код можно строить, приписывая к каждой комбинации безызбыточного кода остаток от деления соответствующего этой комбинации многочлена на образующий многочлен кода. Для кодов, число информационных символов в которых больше числа проверочных, рассмотренный способ реализуется наиболее просто.

Следует указать еще на один способ кодирования. Так как циклический код является разновидностью группового кода, то его проверочные символы должны выражаться через суммы по модулю два определенных информационных символов.

Равенства для определения проверочных символов могут быть получены путем решения рекуррентных соотношений:

где h — двоичные коэффициенты так называемого генераторного многочлена h(x), определяемого так

Соотношение (6.40) позволяет по заданной последовательности информационных сигналов a₀, a₁,..., a_k-1, вычислить n — k проверочных символов a_k, a_k+1,...,а_n-1. Проверочные символы, как и ранее, размещаются на местах младших разрядов. При одних и тех же информационных символах комбинации кода, получающиеся таким путем, полностью совпадают с комбинациями, получающимися при использовании предыдущего способа кодирования. Применение данного способа целесообразно для кодов с числом проверочных символов, превышающим число информационных, например, для кодов Боуза — Чоудхури — Хоквингема.

Матричная запись циклического кода. Полная образующая матрица циклического кода Mn,k составляется из двух матриц: единичной I_k (соответствующей k информационным разрядам) и дополнительной C_k,n-k (соответствующей проверочным разрядам):

Построение матрицы I_k трудностей не представляет.

Если образование циклического кода производится на основе решения рекуррентных соотношений, то его дополнительную матрицу можно определить, воспользовавшись правилами, указанными ранее. Однако обычно строки дополнительной матрицы циклического кода C_k,n-k определяются путем вычисления многочленов r(х). Для каждой строки матрицы Ik соответствующий r(х) находят делением информационного многочлена а(х)х^m этой строки на образующий многочлен кода g(x).

Дополнительную матрицу можно определить и не строя I_k. Для этого достаточно делить на g(x) комбинацию в виде единицы с рядом нулей и получающиеся остатки записывать в качестве строк дополнительной матрицы. При этом если степень какого-либо r(х) оказывается меньше n — k— 1, то следующие за этим остатком строки матрицы получают путем циклического сдвига предыдущей строки влево до тех пор, пока степень r(х) не станет равной n — k—1. Деление производится до получения k строк дополнительной матрицы.

Пример 6.14. Запишем образующую матрицу для циклического кода (15,11) с порождающим многочленом g(x) = x⁴ + x³ + 1 ·

Воспользовавшись результатами ранее проведенного деления, получим

Существует другой способ построения образующей матрицы, базирующийся на основной особенности циклического (n, k)-кода (см § 6.6). Он проще описанного, но получающаяся матрица менее удобна.

Матричная запись кодов достаточно широко распространена.

Укороченные циклические коды. Корректирующие возможности циклических кодов определяются степенью m образующего многочлена. В то время как необходимое число информационных символов может быть любым целым числом, возможности в выборе разрядности кода весьма ограничены.

Если, например, необходимо исправить единичные ошибки при k = 5, то нельзя взять образующий многочлен третьей степени, поскольку он даст только семь остатков, а общее число разрядов получится равным 8.

Следовательно, необходимо брать многочлен четвертой степени и тогда n= 15. Такой код рассчитан на 11 информационных разрядов.

Однако можно построить код минимальной разрядности, заменив в (n, k) -коде j первых информационных символов нулями и исключив их из кодовых комбинаций. Код уже не будет циклическим, поскольку циклический сдвиг одной разрешенной кодовой комбинации не всегда приводит к другой разрешенной комбинации того же кода. Получаемый таким путем линейный (n — j, k — j)-код называют укороченным циклическим кодом. Минимальное расстояние этого кода не менее, чем минимальное кодовое расстояние (n, k)-кода, из которого он получен. Матрица укороченного кода получается из образующей матрицы (n, k)-кода исключением j строк и столбцов, соответствующих старшим разрядам. Например, образующая матрица кода (9,5), полученная из матрицы кода (15,11), имеет вид

 

§ 6.8 ТЕХНИЧЕСКИЕ СРЕДСТВА КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДЛЯ ЦИКЛИЧЕСКИХ КОДОВ

 

Линейные переключательные схемы. Основу кодирующих и декодирующих устройств циклических кодов составляют регистры сдвига с обратными связями, позволяющие осуществлять как умножение, так и деление многочленов с приведением коэффициентов по модулю два. Такие регистры также называют многотактными линейными переключательными схемами и линейными кодовыми фильтрами Хаффмена. Они состоят из ячеек памяти, сумматоров по модулю два и устройств умножения на коэффициенты многочленов множителя или делителя. В случае двоичных кодов для умножения на коэффициент, равный 1, требуется только наличие связи в схеме. Если коэффициент равен 0, то связь отсутствует. Сдвиг информации в регистре осуществляется импульсами, поступающими с генератора продвигающих импульсов, который на схеме, как правило, не указывается. На вход устройств поступают только коэффициенты многочленов, причем начиная с коэффициента при переменной в старшей степени.

На рис. 6.10 представлена схема, выполняющая умножение произвольного (например, информационного) многочлена а(х)g(x) = а₀+а₁х+...+a_k-1*x^k-1 на некоторый фиксированный (например, образующий) многочлен g(х)=g₀+g₁ +...+g_n-k*x^n-k. Произведение этих многочленов равно