Шпаргалка: Лекции по количественной оценке информации

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

Таблица 6.1

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

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

Тривиальные систематические коды.

Код Хэмминга

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

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

Код Хэмминга является типичным примером систематического кода. Однако при его построении к матрицам обычно не прибегают. Для вычисления основных параметров кода задается либо количество информационных символов, либо количество информационных комбинаций . При помощи (59) и (60) вычисляются  и . Соотношения между  для кода Хэмминга представлены в табл. 1 приложения 8. Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочими, а какие контрольными. Как показала практика, номера контрольных символов удобно выбирать по закону , где  и т.д. - натуральный ряд чисел. Номера контрольных символов в этом случае будут соответственно: 1, 2, 4, 8, 16, 32 и т. д.

Затем определяют значения контрольных коэффициентов (0 или 1), руководствуясь следующим правилом: сумма единиц на контрольных позициях должна быть четной. Если эта сумма четна, то значение контрольного коэффициента - 0, в противном случае - 1.

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

Первой строке соответствует проверочный коэффициент , второй  и т.д., как показано в табл. 2 приложения 8. Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу: в первую проверку входят коэффициенты, которые содержат в младшем разряде 1, т.е.  и т. д.; во вторую - коэффициенты, содержащие 1 во втором разряде, т.е.  и т.д.; в третью проверку - коэффициенты, которые содержат 1 в третьем разряде, и т. д. Номера проверочных коэффициентов соответствуют номерам проверочных позиций, что позволяет составить общую таблицу проверок (табл. 3, приложение 8). Старшинство разрядов считается слева направо, а при проверке сверху вниз. Порядок проверок показывает также порядок следования разрядов в полученном двоичном коде.

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

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

Циклические коды

Циклические коды [4, 6, 7, 9, 12, 13] названы так потому, что в них часть комбинаций кода либо все комбинации могут быть получены путем циклического сдвига одной или нескольких комбинаций кода. Циклический сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец комбинации. Циклические коды, практически[13], все относятся к систематическим кодам, в них контрольные и информационные разряды расположены на строго определенных местах. Кроме того, циклические коды относятся к числу блочных кодов. Каждый блок (одна буква является частным случаем блока) кодируется самостоятельно.

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

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

Предположим, требуйся закодировать одну из комбинаций четырехзначного двоичного кода. Предположим также, что эта комбинация - . Пока не обосновывая свой выбор, берем из таблицы неприводимых многочленов (табл. 2, приложение 9) в качестве образующего многочлен . Затем умножим  на одночлен той же степени, что и образующий многочлен. От умножения многочлена на одночлен степени п степень каждого члена многочлена повысится на , что эквивалентно приписыванию  нулей со стороны младших разрядов многочлена. Так как степень выбранного неприводимого многочлена равна трем, то исходная информационная комбинация умножается на одночлен третьей степени:

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

Значение корректирующих разрядов находят по результату от деления  на :

или

Таким образом,

или в общем виде

                                                          (75)

где  - частное, a  - остаток от деления  на .

Так как в двоичной арифметике , а значит, , то можно при сложении двоичных чисел переносить слагаемые из одной части равенства в другую без изменения знака (если это удобно), поэтому равенство вида  можно записать и как  и как . Все три равенства в данном случае означают, что либо  и  равны 0, либо а и  равны 1, т. е. имеют одинаковую четность.

Таким образом, выражение (75) можно записать как

                                       (76)

что в случае нашего примера даст

или

Многочлен 1101001 и есть искомая комбинация, где 1101 - информационная часть, а 001 - контрольные символы. Заметим, что искомую комбинацию мы получили бы и как в результате умножения одной из комбинаций полного четырехзначного двоичного кода (в данном случае 1111) на образующий многочлен, так и умножением заданной комбинации на одночлен, имеющий ту же степень, что и выбранный образующий многочлен (в нашем случае таким образом была получена комбинация 1101000) с последующим добавлением к полученному произведению остатка от деления этого произведения на образующий многочлен (в нашем примере остаток имел вид 001).

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

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

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

Циклический сдвиг кодовой комбинации аналогичен умножению соответствующего многочлена на х:

Если степень многочлена достигает разрядности кода, то происходит «перенос» в нулевую степень при . В шифраторах циклических кодов эта операция осуществляется путем соединения выхода ячейки старшего разряда со входом ячейки нулевого разряда. Сложение по модулю 2 любых двух соседних комбинаций циклического кода эквивалентно операции умножения многочлена соответствующего комбинации первого слагаемого на многочлен  если приведение подобных членов осуществляется по модулю 2:

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

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

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

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

начиная с восьмого, остатки будут повторяться.

Остатки от деления используют для построения образующих матриц, которые, благодаря своей наглядности и удобству получения производных комбинаций, получили широкое распространение для построения циклических кодов. Построение образующей матрицы сводится к составлению единичной транспонированной и дополнительной матрицы, элементы которой представляют собой остатки от деления единицы с нулями на образующий многочлен [15]. Напомним, что единичная транспонированная матрица представляет собой квадратную матрицу, все элементы которой - нули, кроме элементов, расположенных по диагонали справа налево сверху вниз (в нетранспонированной матрице диагональ с единичными элементами расположена слева направо сверху вниз). Элементы дополнительной матрицы приписываются справа от единичной транспонированной матрицы.

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

Строки образующей матрицы представляют собой первые комбинации искомого кода. Остальные комбинации кода получаются в результате суммирования по модулю 2 всевозможных сочетаний строк образующей матрицы[16].

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

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

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

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

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

                                                  (77)

где  - число информационных разрядов кода[17].

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

                                                                            (78)

где  - длина кодовой комбинации.

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

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

Идея исправления ошибок базируется на том, что ошибочная комбинация после определенного числа циклических сдвигов “ подгоняется ” под остаток таким образом, что в сумме с остатком она дает исправленную комбинацию. Остаток при этом представляет собой не что иное, как разницу между искаженными и правильными символами, единицы в остатке стоят как раз на местах искаженных разрядов в подогнанной циклическими сдвигами комбинации. Подгоняют искаженную комбинацию до тех пор, пока число единиц в остатке не будет равно числу ошибок в коде. При этом, естественно, число единиц может быть либо равно числу ошибок , исправляемых данным кодом (код исправляет 3 ошибки и в искаженной комбинации 3 ошибки), либо меньше s (код исправляет 3 ошибки, а в принятой комбинации - 1 ошибка).

Место ошибки в кодовой комбинации не имеет значения. Если  то после определенного количества сдвигов все ошибки окажутся в зоне “разового” действия образующего многочлена, т. е. достаточно получить один остаток, вес которого , и этого уже будет достаточно для исправления искаженной комбинации. В этом смысле коды БЧХ (о них мы будем говорить ниже) могут исправлять пачки ошибок, лишь бы длина пачки не превышала s.

Построение и декодирование конкретных циклических кодов

I.          Коды, исправляющие одиночную ошибку, .

1. Расчет соотношения между контрольными и информационными символами кода производится на основании выражений (59) - (69).

Если задано число информационных разрядов , то число контрольных разрядов  находим из выражения

Общее число символов кода

Если задана длина кода , то число контрольных разрядов

Соотношение числа контрольных и информационных символов для кодов с  приведены в табл. 3 приложения 9.

2. Выбор образующего многочлена производится по таблицам неприводимых двоичных многочленов.

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

3. Выбор параметров единичной транспонированной матрицы происходит из условия, что число столбцов (строк) матрицы определяется числом информационных разрядов, т. е. ранг единичной матрицы равен .

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

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

Страницы: 1, 2, 3, 4