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

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

Данные коды являются разновидностью ЦК и позволяют корректировать как независимые, так и пакетные ошибки и параметры кодов находятся через элементы расширенного поля Галуа, суть которого состоит в следующем [3,4,6,7].

Пусть Р(х) является образующим полиномом кодовой последовательности F_i(x) некоторого ЦК. Так как Р(х) относится к примитивному полиному, т. е. который не раскладывается на сомножители более низких степеней, чем степень полинома Р(х), то можно найти корни полинома при которых Р(х)=0.

Пусть m ₁, m ₂, m ₃,… m _{2∙ tисп -1} – корни некоторого примитивного полинома, и которые, в свою очередь, являются степенями некоторых минимальных (примитивных) полиномов соответственно: m ₁(х), m ₂(х), m ₃,… m _{2∙ tисп -1} (х). Тогда, если F_i(x) принадлежит ЦК, то кодовая последовательность F_i(x) должна делиться без остатка на образующий полином вида Р(х)=НОК[m ₁ (х)∙m ₃ (х)∙…∙ m _{2∙ tисп -1} (х) ], т. е. НОК произведения минимальных нечетных полиномов.

Порядок (количество) минимальных полиномов определяется как i=2∙t_исп-1. Существуют минимальные полиномы одного и того же порядка (i), но с различными значениями степеней (γ). Максимальная степень произведения минимальных полиномов (m_i), входящих в полином Р(х), должна быть равна величине l=n-k, которая и определяет длину кодовой последовательности по формуле n=2^l-1=2^ε-1 двоичных символов.

Так как порядок (номер) самого старшего минимального полинома Р(х) равен 2∙t_исп-1, то количество полиномов (β), входящих в образующий полином Р(х), равно кратности исправляемых ошибок, т. е. β = t_исп.

Например, если t_исп=5 двоичных символов, то 2∙t_исп-1=9 и в выражение Р(х) будут входить β=5 минимальных полиномов: m₁(х), m₃(х), m₅(х), m₇(x) и m₉(x). Минимальные полиномы для большинства БЧХ-кодов табулированы [1-3].

Для нахождения образующего полинома Р(х) по формуле Р(х)=НОК[m ₁ (х)∙m ₃ (х)∙…∙ m _{2∙ tисп -1} (х) ] необходимо выписать из требуемой таблицы все значения табулированных минимальных полиномов, соответствующих степени ε (соответствующий столбец таблицы) до порядка i=2∙t_исп-1 (соответствующая строка таблицы) включительно. При отсутствии в таблице минимального полинома «нужного» порядка необходимо выбрать ближайший меньший, а если среди минимальных полиномов окажется два одинаковых, то для выражения Р(х) необходимо взять только один полином.

Для определения параметров БЧХ-кода необходимо, чтобы было задано: n – длина кодовой последовательности и t_исп – длина или кратность исправляемых ошибок.

Пример 2.6. Определить параметры БЧХ-кода корректирующего t_исп≤ 2- х кратные ошибки на длине кодовой последовательности n=15 двоичных символов.

Решение:

а) из равенства-неравенства n ≤ 2^ε-1 определяем степень минимальных полиномов, входящих в Р(х); одновременно определяем номер столбца табулированных корней образующего полинома [4,s]: n=15=2^ε-1, откуда 16=2^ε, а ε=4;

б) определяем порядок корней образующего полинома, т.е. i=2∙t_исп =2∙2-1=3, что также определяет номер строки, (3-я строка) табулированных корней образующего полинома;

в) из таблицы 4.1 [4] для i=3 -ей строки и ε=4 -го столбца выписываем минимальные полиномы, которые заданы в восьмеричной форме записи, а именно: m₁(x)=23, m₃(x)=37, которые будут иметь следующие степени: m₁(x)=010011=х⁴+х+1, m₃(x)=01111=х⁴+х³+х²+х+1. Следовательно, искомый образующий полином для заданного кода можно записать в виде Р(х)=НОК[(х⁴+х+1)∙(х⁴+х³+х²+х+1)]=х⁸+х⁷+х⁶+х⁴+1;

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

1) l=ε(d-1)/2=4(5-1)/2=8 двоичных символов;

2) l≥ε∙t_исп=4∙2=8 двоичных символов;

3) l=8, т.е. равной максимальной степени Р(х);

д) определяем число информационных символов как:

1) k=n-l=15-8=7 двоичных символов;

2) k=(2^ε-1)-ε∙(d₀-1)/2=(2⁴-1)-4(5-1)/2=7 двоичных символов.

Таким образом, БЧХ-код будет иметь следующие параметры: (n,k,d₀)=(15,7,5) и Р(х)=х⁸+х⁷+х⁶+х⁴+1.

В [3,8] приведены другие варианты построения БЧХ-кодов, как правило, с n ≥ 21 двоичный символ. Кодирование и декодирование БЧХ-кодов может производится различными способами, которые рассматриваются в следующем разделе.

В реальных системах связи широкое применение для коррекции одиночных пакетов ошибок получили ЦК, способ построения которых был разработан Файром.

2.2.5 Способ построения кодовых последовательностей циклического кода с использованием образующего полинома вида P(x)=s(x)∙(x^c+1)

Способ задания ЦК с использованием образующего полинома вида P(x)=s(x)∙(x^c+1) был предложен Файром и поэтому были названы кодами Файра.

Циклические коды Файра используются для обнаружения и коррекции одиночных пакетов ошибок любой длины (t_n), разделенных безошибочным интервалом в l _защ ≥ (n-t_n) двоичных символов. Как уже отмечалось, данные коды задаются образующим полиномом вида [1-3,5-9]

P(x) = s(x)∙(x^с+1), (2.9)

где s(x) – неприводимый полином максимальная степень которого равна кратности исправляемого пакета ошибок, т.е. ε ≥ l _{n исп}; с – степень двучлена, равная или больше t_{n исп}+t_{n обн}-1; t_{n обн} – длина или кратность обнаруживаемого пакета ошибок.

Величина «с» не должна делиться на некоторое число χ=2^{tn исп}-1. Если использовать ЦК Файра только для обнаружения пакетных ошибок, то для этого необходимо, чтобы количество проверочных символов кода соответствовало следующему равенству-неравенству l ≥ t_{n обн} двоичных символов, а при коррекции t_n ошибок l ≥ 2∙t_{n исп .}.

Длина кодовой последовательности «n» данных кодов определяется равенством n=НОК[χ,c] двоичных символов. Минимальное кодовое расстояние кода определяется равенством-неравенством вида d₀≥t_{n исп.}+t_{n обн}+1.

Пример 2.7. Рассчитать параметры ЦК Файра корректирующего пакет ошибок кратностью t_{n исп} ≤ 3 двоичных символов и обнаруживающего пакет ошибок кратностью t_{n исп} ≤ 4 двоичных символа.

Решение:

а) выбираем неприводимый полином s(x) степени ε = t_{n исп}=3, т.е. s(x)=х³+х+1;

б) определяем степень «с» двучлена (x^с+1) по формуле:

с = t_{n исп.} + t_{n обн}-1=3+4-1=6;

в) вычисляем образующий полином по формуле:

P(x)=s(x)∙(x^с+1)=(х³+х+1) (х⁶+1)=х⁹+х⁷+х⁶+х³+х+1;

г) определяем количество проверочных символов по формуле l ≥ c+t = 6+3=9 двоичных символов, что равно максимальной степени образующего полинома Р(х);

д) вычисляем величину χ по формуле χ=2^{tn исп}-1=2³-1=7;

е) определяем длину кодовой последовательности кода, т. е. n=НОК[χ,c]=НОК[7,6]=42 двоичных символа;

ё) определяем количество информационных символов, как k=n-l=42-9=33 двоичных символа;

ж) находим минимальное кодовое расстояние кода по формуле d₀ ≥ t_{n исп.}+t_{n обн}+1=3+4+1=8.

Таким образом, циклический код Файра имеет следующие параметры: (n,k,d₀)=(48,33,8) и P(x)=х⁹+х⁷+х⁶+х³+х+1.