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

d ₀ ³ 5

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

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

Для исправления числа ошибок s ³ 2 еще не достаточно условия, чтобы между комбинациями кода минимальное кодовое расстояние d₀ = 2 s + 1, необходимо также чтобы длина кода n удовлетворяла условию

n = 2 ^h - 1,

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

r £ h • s = [ log₂ (n + 1)]

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

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

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

2 ^h - 1 = n • C

где С является одном из сомножителей, на которые разлагается число n.

Соотношения между n, C и h могут быть сведены в следующую таблицу:

Таблица 5.14 – Соотношения между h, n, C

№ п/п	h	n = 2 ^h - 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), которые являются простыми неприводимыми многочленами.

Таблица 5.15 – Минимальные неприводимые многочлены в поле Галуа GF (2) степени от 2 до 7

Степень
					1010111* 1001001*
Степень

Таблица 5.16 – Минимальные неприводимые многочлены в поле Галуа GF (2) степени от 8 до 10

Степень
	101110111* 111110011* 110111101* 111010111* 110001011* 100011011* 100111111*	1010011001* 1000010111*	10000001111* 10010101111* 10000110101* 10110101011* 11111101011* 11101111011*

Примечание:

Неприводимый многочлен степени m над полем GF (q) называется примитивным, если:

· его корнем является примитивный элемент поля GF (q^m);

· когда принадлежит показателю q^m – 1;

· когда он не является делителем многочлена xⁿ – 1 при n, меньших, чем q^m – 1.

Звездочкой обозначены все непримитивные многочлены.

Образующий многочлен представляет собой произведение нечетных минимальных многочленов и является их наименьшим общим кратным (НОК). Максимальный порядок r определяет номер последнего из выбираемых табличных минимальных многочленов

g = 2 s - 1.

Порядок многочлена используется при определении числа сомножителей P(x). Например, если s = 6, то r = 2 s - 1 = 11. Так как для построения P(x) используются только нечетные многочлены, то ими будут: M₁(x), M₃(x), M₅(x), M₇(x), M₉(x), M₁₁(x), старший из них имеет порядок r. Как видим, число сомножителей P(x) равно 6, т. е. числу исправляемых ошибок. Таким образом, число минимальных многочленов, участвующих в построении образующего многочлена

L = s,

а старшая степень l = h

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

Степень образующего многочлена, полученного в результате перемножения выбранных минимальных многочленов,

b = r £ l •s = h •s.

В общем виде

P(x) = НОК [ M₁(x) • M₃(x) •... • M_r(x) ].

Декодирование кодов БЧХ производится по той же методике, что и декодирование циклических кодов с d₀ < 5. Однако в связи с тем, что практически все коды БЧХ представлены комбинациями с n ³ 15, могут возникнуть весьма сложные варианты, когда для обнаружения и исправления ошибок необходимо производить большое число циклических сдвигов. В этом случае для облегчения можно комбинацию, полученную после k - кратного сдвига и суммирования с остатком, сдвигать не вправо, а влево на n – k циклических сдвигов. Это целесообразно делать только при k > n/2.

Дата добавления: 2014-01-06