Быстрый поиск

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

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

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

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

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

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

(77)

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

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

(78)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

в) число единиц каждого остатка, т. е. его вес, должно быть не менее величины , где - минимальное кодовое расстояние, не меньшее числа обнаруживаемых ошибок;

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

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

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

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

а) принятую комбинацию делят на образующий многочлен и

б) подсчитывают количество единиц в остатке (вес остатка).

Если , где s - допустимое число исправляемых данным кодом ошибок, то принятую комбинацию складывают по модулю 2 с полученным остатком. Сумма даст исправленную комбинацию. Если , то

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

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

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

е) производят циклический сдвиг вправо ровно на столько разрядов, на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную комбинацию[18].

II. Коды, обнаруживающие трехкратные ошибки, .

1. Выбор числа корректирующих разрядов производится из соотношения

или

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

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

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

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

5. Обнаружение ошибок производится по остаткам от деления принятой комбинации на образующий многочлен . Если остатка нет, то контрольные разряды отбрасываются и информационная часть кода используется по назначению. Если в результате деления получается остаток, то комбинация бракуется. Заметим, что такие коды могут обнаруживать 75% любого количества ошибок, так как кроме двойной ошибки обнаруживаются все нечетные ошибки, но гарантированное количество ошибок, которое код никогда не пропустит, равно 3.

Пример: Исходная кодовая комбинация - 0101111000, принятая - 0001011001 (т. е. произошел тройной сбой). Показать процесс обнаружения ошибки, если известно, что комбинации кода были образованы при помощи многочлена 101111.

Решение:

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

III. Циклические коды, исправляющие две и большее количество ошибок,

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

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

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

(79)

при этом п всегда будет нечетным числом. Величина h определяет выбор числа контрольных символов и связана с и s следующим соотношением:

(80)

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

(81)