Построение и декодирование конкретных циклических кодов
3.5.1 Коды исправляющие одиночную ошибку d0 = 3
1. Расчет соотношений между контрольными и информационными символами кода производится на основании следующих выражений.
Если задано число информационных разрядов k, то число контрольных разрядов r находим из выражения
r = [ log2 {( k + 1 ) + log2 ( k + 1 )}].
Общее число символов кода
n = k + r
Если задана длина кода n, то число контрольных разрядов
r = [ log2 ( n + 1 ) ].
2. Выбор образующего многочлена производится по таблицам неприводимых двоичных многочленов.
Таблица 3.5.1.1 – Фрагменты таблицы образующих многочленов
| Коды многочленов | ||||
Образующий многочлен P(x) следует выбирать как можно более коротким, но степень его должна быть не менее числа контрольных разрядов r, а число нулевых членов ‑ не меньше минимального кодового расстояния d0.
3. Выбор параметров единичной транспонированной матрацы происходит из условия, что число столбцов (строк) матрицы определяется числом информационных разрядов, т. е. ранг единичной матрицы равен k.
4. Определение элементов дополнительной матрицы производится по остаткам от деления последней строки транспонированной матрицы (единицы с нулями) на образующий многочлен.
Полученные остатки должны удовлетворять следующим требованиям:
а) число разрядов каждого остатка должно быть равно числу контрольных символов r, следовательно, число разрядов дополнительной матрицы должно быть равно степени образующего многочлена;
б) число остатков должно быть не меньше числа строк единичной транспонированной матрицы, т. е. должно быть равно числу информационных разрядов k.
в) число единиц каждого остатка, т. е. его вес, должно быть не менее величины r = d0 - 1, где d0 ‑ минимальное кодовое расстояние, не меньшее числа обнаруживаемых ошибок;
г) количество нулей, приписываемых к единице с нулями при делении ее на выбранный многочлен, должно быть таким, чтобы соблюдались условия а), б), в).
5. Образующая матрица составляется дописыванием элементов дополнительной матрицы справа от единичной транспонированной матрицы либо умножением элементов единичной матрицы на образующий многочлен.
6. Комбинациями исходного кода являются строки образующей матрицы и все возможные суммы по модулю 2 различных сочетаний строк образующей матрицы.
7. Обнаружение и исправление ошибок производится по остаткам от деления принятой комбинации F(x) на образующий многочлен P(x). Если принятая комбинация делится на образующий многочлен без остатка, то код принят без ошибок. Остаток от деления свидетельствует о наличии ошибки, но не указывает, какой именно.
Для того чтобы найти ошибочный разряд и исправить его в циклических кодах, осуществляют следующие операции:
а) принятую комбинацию делят на образующий многочлен и
б) подсчитывают количество единиц в остатке (вес остатка). Если W £ s, где s ‑ допустимое число исправляемых данным кодом ошибок, то принятую комбинацию складывают по модулю 2 с полученным остатком. Сумма даст исправленную комбинацию. Если W > s, то
в) производят циклический сдвиг принятой функции F(x) влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на P(x). Если в результате этого деления W £ s, то делимое суммируется с остатком, затем
г) производится циклический сдвиг вправо на один разряд комбинации, полученной в результате суммирования последнего делимого с последним остатком. Полученная в результате комбинация уже не содержит ошибок. Если после первого циклического сдвига и последующего деления остаток получается таким, что его вес W > s, то
д) повторяют операцию пункта в) до тех пор, пока не будет W £ s. В этом случае комбинацию, полученную в результате циклического сдвига, суммируют с остатком от деления этой комбинации на образующий многочлен, а затем
е) производят циклический сдвиг вправо ровно на столько разрядов, на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную
комбинацию.
Пример.
Построить все комбинации циклического кода, исправляющего одиночные ошибки в каждой комбинации кода. Число различных комбинаций кода должно обеспечивать передачу 26 букв латинского алфавита.
Показать процесс исправления ошибки в одной из комбинаций, полученной в результате суммирования нескольких строк образующей матрицы.
Решение.
Определяем число информационных разрядов
Тогда число корректирующих разрядов
Выбираем образующий многочлен
Строим образующую матрицу
по которой находим разрешенные комбинации кода:
1) 0 0 0 0 1 ´ 1 0 0 1 1
2) 0 0 0 1 0 ´ 1 0 0 1 1
3) 0 0 1 0 0 ´ 1 0 0 1 1
4) 0 1 0 0 0 ´ 1 0 0 1 1
5) 1 0 0 0 0 ´ 1 0 0 1 1
6) a1 Å a2 = 0 0 0 1 1 0 1 0 1;
7) a1 Å a3 = 0 0 1 0 1 1 1 1 1;
8) a1 Å a4 = 0 1 0 0 0 1 0 1 1;
9) a1 Å a5 = 1 0 0 1 0 0 0 1 1;
10) a2 Å a3 = 1 0 1 1 0 1 0 1 0;
11) a2 Å a4 = 0 1 0 1 1 1 1 1 0;
12) a2 Å a5 = 1 0 0 0 1 0 1 1 0;
13) a3 Å a4 = 0 1 1 0 1 0 1 0 0;
14) a3 Å a5 = 1 0 1 1 1 1 1 0 0;
15) a3 Å a5 = 1 1 0 1 0 1 0 0 0;
16) a1 Å a2 Å a3 = 0 0 1 1 1 1 0 0 1;
17) a1 Å a2 Å a4 = 0 1 0 1 0 1 1 0 1;
18) a1 Å a2 Å a5 = 1 0 0 0 0 0 1 0 1;
19) a1 Å a3 Å a4 = 0 1 1 0 0 0 1 1 1;
20) a1 Å a3 Å a5 = 1 0 1 1 0 1 1 1 1;
21) a1 Å a4 Å a5 = 1 1 0 1 1 1 0 1 1;
22) a2 Å a3 Å a4 = 0 1 1 1 1 0 0 1 0;
23) a2 Å a3 Å a5 = 1 0 1 0 1 1 0 1 0;
24) a2 Å a4 Å a5 = 1 1 0 0 0 1 1 1 0;
25) a3 Å a4 Å a5 = 1 1 1 1 0 0 1 0 0;
26) a1 Å a2 Å a3 Å a4 = 0 1 1 1 0 0 0 0 1;
27) a1 Å a2 Å a3 Å a5 = 1 0 1 0 0 1 0 0 1;
28) a1 Å a2 Å a4 Å a5 = 1 1 0 0 1 1 1 0 1;
29) a1 Å a3 Å a4 Å a5 = 1 1 1 1 1 0 1 1 1;
30) a2 Å a3 Å a4 Å a5 =1 1 1 0 0 0 0 1 0;
31) a1 Å a2 Å a3 Å a4 Å a5 = 1 1 1 0 1 0 0 0 1;
Для передачи 26 букв латинского алфавита можно выбрать любые 26 из полученных 31 комбинации.
Исправление ошибки.
Предположим, ошибка произошла в комбинации № 29, т.е. принятая комбинация - 111110110.
Исправляем ошибку
1 1 1 1 1 0 1 1 0 1 0 0 1 1
1 0 0 1 1
1 1 0 0 0
1 0 0 1 1 W = s
1 0 1 1 1
1 0 0 1 1
1 0 0 1 0
1 0 0 1 1
1
Так как получили W = s то суммируем остаток с принятой кодовой комбинацией и тем самым получаем исправленную комбинацию.
1 1 1 1 1 0 1 1 0
1
1 1 1 1 1 0 1 1 1
3.5.2 Циклические коды, исправляющие две и большее количество ошибок, d0 ³ 5
Методика построения циклических кодов с d0 ³ 5 отличается от методики построения циклических кодов с d0 < 5 только в выборе образующего многочлена. В литературе эти коды известны как БЧХ (первые буквы фамилий Боуз, Чоудхури, Хоквинхем ‑ авторов методики построения циклических кодов с d0 ³ 5).
Построение образующего многочлена зависит, в основном, от двух параметров: от длины кодового слова n и от числа исправляемых ошибок s. Остальные параметры, участвующие в построении образующего многочлена, в зависимости от заданных n и s могут быть определены при помощи таблиц и вспомогательных соотношений, о которых будет сказано ниже.
Для исправления числа ошибок s ³ 2 еще не достаточно условия, чтобы между комбинациями кода минимальное кодовое расстояние d0 = 2s + 1, необходимо также чтобы длина кода n удовлетворяла условию
n = 2h - 1,
при этом n всегда будет нечетным числом. Величина h определяет выбор числа контрольных символов r и связана с r и s следующим соотношением:
r £ h • s = [ log2 (n + 1)]
С другой стороны, число контрольных символов определяется образующим многочленом и равно его степени.
При больших значениях h длина кода n становится очень большой, что вызывает вполне определенные трудности при технической реализации кодирующих и декодирующих устройств. При этом часть информационных разрядов порой остается неиспользованной.
В таких случаях для определения h удобно пользоваться выражением
2h - 1 = n • C
где С является одном из сомножителей, на которые разлагается число n.
Соотношения между n, C и h могут быть сведены в следующую таблицу:
Таблица 3.5.2.1 – Соотношения между h, n, C
| № п/п | h | n = 2h - 1 | C |
| 5; 3 | |||
| 7; 3; 3 | |||
| 17; 5; 3 | |||
| 7; 3; 7 | |||
| 31; 11; 3 | |||
| 89; 23 | |||
| 3; 3 ;5 ; 7; 13 |
Пример.
При h = 10 длина кодовой комбинации может быть равна и 1023 (С = 1), и 341 (С = 3), и 33 (С = 31), 31 (С = 33), понятно что n не может быть меньше r ³ h •s.
Величина С влияет на выбор порядковых номеров минимальных многочленов, так как индексы первоначально выдранных многочленов умножаются на С.
Построение образующего многочлена P(x) производится при помощи так называемых минимальных многочленов M(x), которые являются простыми неприводимыми многочленами.
Таблица 3.5.2.2 – Минимальные неприводимые многочлены в поле Галуа GF (2) степени от 2 до 7
| Степень | ||||||
| 1010111* 1001001* | ||||||
| Степень |
Таблица 3.5.2.3 – Минимальные неприводимые многочлены в поле Галуа GF (2) степени от 8 до 10
| Степень | |||
| 101110111* 111110011* 110111101* 111010111* 110001011* 100011011* 100111111* | 1010011001* 1000010111* | 10000001111* 10010101111* 10000110101* 10110101011* 11111101011* 11101111011* |
Примечание:
Неприводимый многочлен степени m над полем GF (q) называется примитивным, если:
· его корнем является примитивный элемент поля GF (qm);
· когда принадлежит показателю qm – 1;
· когда он не является делителем многочлена xn – 1 при n, меньших, чем qm – 1.
Звездочкой обозначены все непримитивные многочлены.
Образующий многочлен представляет собой произведение нечетных минимальных многочленов и является их наименьшим общим кратным (НОК). Максимальный порядок r определяет номер последнего из выбираемых табличных минимальных многочленов
g = 2s - 1.
Порядок многочлена используется при определении числа сомножителей P(x). Например, если s = 6, то r = 2s - 1 = 11. Так как для построения P(x) используются только нечетные многочлены, то ими будут: M1(x), M3(x), M5(x), M7(x), M9(x), M11(x), старший из них имеет порядок r. Как видим, число сомножителей P(x) равно 6, т. е. числу исправляемых ошибок. Таким образом, число минимальных многочленов, участвующих в построении образующего многочлена
L = s,
а старшая степень
l = h
(l указывает колонку в столбце минимальных многочленов, из которой обычно выбирается многочлен для построения P(x)).
Степень образующего многочлена, полученного в результате перемножения выбранных минимальных многочленов,
b = r £ l •s = h •s.
В общем виде
P(x) = НОК [M1(x) • M3(x) • . . . • Mr(x)].
Декодирование кодов БЧХ производится по той же методике, что и декодирование циклических кодов с d0 < 5. Однако в связи с тем, что практически все коды БЧХ представлены комбинациями с n ³ 15, могут возникнуть весьма сложные варианты, когда для обнаружения и исправления ошибок необходимо производить большое число циклических сдвигов. В этом случае для облегчения можно комбинацию, полученную после k - кратного сдвига и суммирования с остатком, сдвигать не вправо, а влево на n – k циклических сдвигов. Это целесообразно делать только при k > n/2.
СЖАТИЕ ИНФОРМАЦИИ
Сжатие информациипредставляет собой операцию, в результате которой данному коду или сообщению ставится в соответствие белее короткий код или сообщение.
Сжатие информации имеет целью - ускорение и удешевление процессов механизированной обработки, хранения и поиска информации, экономия памяти ЭВМ.