Кодирование с использованием циклических кодов

Если дана k - значная входная комбинация m, то n - значное кодовое слово u циклического кода с порождающим полиномом g(x) можно получить двумя способами.

Первый: исходная k - значная комбинация, выраженная в виде полинома

m(x) = m_k-1 x^k-1+…+ m₁ ´ x + m₀ степени (k – 1), умножается на порождающий полином g(x) степени (n – k):

u(x) = m(x) ´g(x).

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

Второй: используется процедура деления полиномов и вычисления остатков. В соответствии с правилами деления полиномов для каждой пары полиномов С(х) и g(x), g(x) ¹ 0 существует единственная пара полиномов q(x) — частное и r(х) — остаток, такие, что

С(х) = q(x)· g(x) Å r(х),

Домножим исходный полином m(x) на x^n-k. Получившийся полином будет иметь степень (k – 1) + (n – k) = (n-1). Представим его в виде

m(x) ·x^n-k = q(x) ·g(x) Å r(х),

где q(x) – частное от деления m(x) ·x^n-k на порождающий полином g(x), а r (х) – остаток от деления. Поскольку степень g(x) равна (n-k), то степень r (x) должна быть (n-k-1) или меньше, а сам полином r (x) будет иметь вид

r(x)= r_{n- k- 1} · x^n-k-1 +...+ r₂ · x²+ r₁ · x +r₀.

С учетом правил арифметики в GF(2) выражение m(x)·x^n-k = q(x)·g(x) Å r(х) можно переписать следующим образом:

r (x) Å x^n-k · m(x) = q(x)· g(x)

откуда видно, что полином r (x) Åx^n-k·m(x) является кратным g(x) и имеет степень n-1 или меньшую. Следовательно, он соответствует свойствам кодовых комбинаций циклических кодов и представляет собой кодовое слово кодируемой информационной последовательности m(x) .

Раскрыв последнее выражение, получим

r (x) Åm(x)·x^n-k = m_k-1 x^n-1+…+ m₁ · x^n-k+1 + m₀ x^n-k +r _{n- k-1} x^n-k-1 +…+r ₁ x +r ₀,

что соответствует кодовому слову u = (m_k-1 … m₁ m₀ r_{n- k-1} r₁ ... r₀).

Таким образом, кодовое слово циклического кода состоит из неизменной информационной части m и (n-k) проверочных символов. Проверочные символы являются коэффициентами полинома r (x), то есть остатка от деления m(x) ·x^n-k на порождающий полином g(x).

Пример. С использованием кода, задаваемого порождающим полиномом g(x) = x³+x+1, закодируем произвольную последовательность, например m=(1001).

Последовательности m =(1001) соответствует полином m (x)= x³+ 1.

Умножим m(x) на x^n-k:

m(x) · x^n-k =m(x) · x³ =(x³+ 1) · x³ = x⁶ + x³.

Разделим m(x) · x^n-k на порождающий полином g(x):

X⁴

X⁴ + 0 + X² + X

X²+ X=r(x).

Таким образом, кодовый полином, соответствующий информационной последовательности m = (1001), будет иметь следующий вид:

U(x) = 1X⁶+ 0X⁵+ 0X⁴ + 1X³ + 1X²+ 1X¹ + 0X⁰,

а соответствующее кодовое слово u = (1001110).

Циклические коды. Важным подклассом линейных блочных кодов являются двоичные циклические коды (cyclic codes). Код легко реализуется на регистре сдвига с обратной связью; на подобных регистрах сдвига с обратной связью вычисляется синдром; алгебраическая структура циклического кода естественным образом позволяет эффективно реализовать методы декодирования. Итак, линейный код (n, к) называется циклическим, если он обладает следующим свойством. Если n-кортеж U= (u₀, u₁, и₂, …, u_n-1) является кодовым словом в подпространстве S, тогда U(1)= (u_n-1, u₀, u₁, и₂,..., u_n-₁), полученный из U с помощью циклического сдвига, также является кодовым словом в S. Или, вообще, U(i) = (u_n-i;. u_n-i+1,…, u_n-1, u₀, u_1,… u_n-i-1), полученный i циклическими сдвигами, является кодовым словом в S.

Циклический код Файра .Циклические коды, обнаруживающие и исправляющие пакеты ошибок (коды Файра). Под пакетом ошибок длиной b понимают такой вид комбинации помехи, в которой между крайними разрядами, пораженными помехами, содержится b-2 разряда. Например, при b=5 комбинации помехи, т.е. пакет ошибок, могут иметь следующий вид: 10001 (поражены тоько два крайних символа), 11111 (поражены все символы), 10111, 11101, 11011 (не поражен лишь один символ), 10011, 11001, 10101 (поражены три символа). При любом варианте непременным условием пакета данной длины является поражение крайних символов.

Коды Файра могут исправлять пакет ошибок длиной b и обнаруживать пакет ошибок длиной b [заметим, что в кодах Файра понятие кодового расстояния - d ].

Коды Боуза-Чоудхури-Хоквингэма.. Эти коды, разработанные Боузом, Чоудхури и Хоквинхемом (сокращенно коды БЧХ), позволяют обнаруживать и исправлять любое число ошибок. Заданными при кодировании является число ошибок s, которое следует исправить, и общее число символов, посылаемых в линию, т.е. длина слов n. Числа информационных символов k и контрольных символов m, а также состав контрольных символов подлежат определению.

Коды БЧХ для обнаружения ошибок. Их строят следующим образом. Если необходимо образовать код с обнаружением четного числа ошибок, то по заданному числу r находят значения d и s. Дальнейшее кодирование выполняют, как и ранее. Если требуются обнаружить нечетное число ошибок, то находят ближайшее меньшее целое число s и кодирование производят так же, как и в предыдущем случае: образующий многочлен дополнительно умножают на двучлен. Например, требуются построить код обнаруживающий семь ошибок при n=15. Находим, что d=8, а ближайшее меньшее значение s=3. Далее определяем многочлен, как указано в примере 3.5, и умножаем его на двучлен, т.е. получаем. Таким образом построен код БЧХ(15,4).

Коды Рида-Соломона (Reed-Solomon code, R-S code) — это недвоичные циклические коды, символы которых представляют собой m-битовые последовательности, где m — положительное целое число, большее 2. Код (n,к) определен на m-битовых символах при всех n и k, для которых

где k - число информационных битов, подлежащих кодированию, а n - число кодовых символов в кодируемом блоке. Для большинства сверточных кодов Рида-Соломона (n, к)

где t - количество ошибочных битов в символе, которые может исправить код, а n-k = 2t- число контрольных символов. Расширенный код Рида-Соломона можно получить при n = 2^m или n= 2^m+ 1, но не более того.

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

Лекция 11.

1. Сверточные коды.

2. Методы декодирования корректирующих кодов. Мягкое и жесткое декодирование. Алгебраическое и мажоритарное декодирование. Сравнение качества декодирования мягких и жестких решений. Декодирование сверточных кодов.

3. Алгоритм Возенкрафта и Фано.

4. Модуляция и кодирование в каналах с ограниченной полосой.

Методы декодирования корректирующих кодов. Существует несколько вариантов декодирования циклических кодов. Один из них заключается в следующем:

1. Вычисление остатка (синдрома). Принятую комбинацию делят на образующий многочлен Р(Х). Остаток R(X)=0 означает, что комбинации принята без ошибок;

2. Подсчет веса остатка W. Если вес остатка равен или меньше числа исправляемых ошибок, т.е. W≤s, то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию;

3. Циклический сдвиг на один символ влево. Если W>s, то производят циклический сдвиг влево и полученную комбинацию снова делят на образующий многочлен. Если вес остатка W≤s, то циклически сдвинутую комбинацию складывают с остатком и затем циклически сдвигают ее в обратную строну вправо на один символ. В результате получают исправленную комбинацию;

4. Дополнительные циклические сдвиги влево. Если после циклического сдвига на один символ по-прежнему W>s, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига сдвинутую комбинацию делят на Р(Х) и проверяют вес остатка. При W≤s выполняют действия, указанные в п.3, с той лишь разницей, что обратных циклических сдвигов вправо делают столько, сколько их было сделано влево.

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

Сверточные коды. Особенностью линейного блочного кода, который описывается двумя целыми числами, n и k, и полиномиальным или матричным генератором является то, что каждый из n-кортежей кодовых слов однозначно определяется k-кортeжeм входного сообщения. Целое число k указывает на число бит данных, которые образуют вход блочного кодера. Целое число n - это суммарное количество разрядов в соответствующем кодовом слове на выходе кодера. Отношение k/n, называемое степенью кодирования кода (code rate), является мерой добавленной избыточности. Сверточный код описывается тремя целыми числами n, k и К, где отношение k/n имеет такое же значение степени кодирования (информация, приходящаяся на закодированный бит), как и для блочного кода; однако n не определяет длину блока или кодового слова, как это было в блочных кодах. Целое число К является параметром, называемым длиной кодового ограничения (constraint length); оно указывает число разрядов k-кортежа в кодирующем регистре сдвига. Важная особенность сверточных кодов, в отличие от блочных, состоит в том, что кодер имеет память - n-кортежи, получаемые при сверточном кодировании, являются функцией не только одного входного k-кортежа, но и предыдущих К-1 входных k-кортежей. На практике n и k - это небольшие целые числа, а К изменяется с целью контроля мощности и сложности кода.

Это и выше редактировать

Цепной алгоритм кодирования, известный также как код Финка – Хагельбергера, является одним из наиболее простых примеров непрерывных кодов. В нем каждый проверочный символ формируется путем сложения двух информационных символов, отстоящих друг от друга на длину памяти L. Вводятся характеристики кода:

k = (L+1) · k₀ - информационная длина слова;

n = (L+1) · n₀ - кодовая длина слова, где n₀ = k₀+r₀.

Кодовая длина слова - это длина кодовой последовательности, на которой сохраняется влияние одного кадра информационных символов.

R = k/n – скорость кода, которая характеризует степень избыточности кода, вводимой для обеспечения исправляющих свойств кода.

Как и блочные, сверточные коды обозначаются как (n,k)- коды.

В частном, наиболее распространенном, случае, k₀ = 1, r₀ = 1, n₀ = k₀+r₀= 2, R = ½.

Хоть избыточность такого кода достаточно велика, но зато он позволяет исправлять пачки ошибок, т.е. непрерывные последовательности ошибочных разрядов. Длина исправляемой пачки зависит от размера памяти кода.

Обозначая последовательность информационных символов через a₀a₁a₂ … a_La_L+1 …, получим следующую последовательность проверочных символов сверточного кода: b₀=a₀Åa_L; b₁=a₁Åa_L+1; … b_L=a_LÅa_2L; b_L+1=a_L+1Åa_2L+1; … В общем потоке символов цепного кода между каждыми двумя информационными разрядами помещается один проверочный (первые L символов удваиваются):

a₀a₀a₁a₁…a_Lb₀a_L+1b₁a_L+2b₂…

Таким образом, каждый символ входной последовательности a_k участвует в формировании двух проверочных символов: b_k-L и b_k. Например, для размера памяти кода L=3 и n₀=2 процесс формирования выходной последовательности выглядит так:

a0

a1

a2

a3

a4

a5

a6

a7

a0

a0

a1

a1

a2

a2

a3

b0

a4

b1

a5

b2

a6

b3

a7

b4

На приеме информационные и проверочные символы разделяются и регистрируются независимо друг от друга. Из принятой последовательности информационных символов формируются контрольные символы с_i по тем же правилам, что и проверочные: c_i = a_iÅa_L+i. Затем каждый контрольный символ c_i сравнивается с соответствующим проверочным символом b_i. Если произошла ошибка в информационном символе, например, a_k, то это вызовет искажение сразу двух контрольных символов: c_k-L и c_k, что и обнаружится в результате их сравнения с проверочными символами b_k-L и b_k. Отсюда по общему индексу k легко определить и исправить ошибку. Ошибка в принятом проверочном символе, например, b_k, приводит к несовпадению контрольной и проверочной последовательностей лишь в одном месте. Исправление такой ошибки не требуется. Видно, что проверку надо производить с задержкой на 2L.

Дата добавления: 2014-10-22