// Поиск. Серия естественных и технических наук. – 2007. – №4. – С.213-216.

УДК 681.3.07

систематическое  кодирование  и обнаружение ошибок

с помощью (n – k)  –  разрядного регистра сдвига линейных циклических кодов

Евразийский национальный университет им. , г. Астана

Систематическое кодирование с (n – k)  –  разрядным регистром сдвига

В статье [1] было показано, что кодирование с помощью циклического кода в систематической форме включает в себя вычисление битов четности, как результат деления по модулю g(X), т. е., деление смещенного вправо (смещенного вверх) многочлена сообщения на порождающий многочлен  g(X). Сдвиг вправо приводит к освобождению места для битов четности, которые прибавляются к разрядам сообщения, что в результате дает вектор кода в систематической форме. На n – k разрядов сообщения сдвиг вправо является тривиальной операцией и в действительности не выполняется в схеме деления. На самом деле вычисляются только биты четности, затем они помещаются на соответствующие места рядом с битами сообщения. Многочлен четности – это остаток от деления на порождающий многочлен  g(X). Он находится в регистре после п сдвигов через (n – k) – разрядный  регистр сдвига с обратной связью. Заметим, что первые n – k сдвигов по разрядам – это просто заполнение регистра. Однако никакой обратной связи не будет, пока не будет заполнен крайний справа разряд. Следовательно, надо сократить цикл деления, загружая входные данные с выхода последнего разряда, как показано на рисунке 1.

НЕ нашли? Не то? Что вы ищете?

Рисунок 1– Кодирование с помощью (n – k) – разрядного 

регистра сдвига

В крайнем левом разряде слагаемое обратной связи является суммой входных данных и крайнего пра­вого разряда. Чтобы создавалась эта сумма, необходимо выполнение условия g0 = gn-k = 1 для произ­вольного порождающего многочлена  g(X).  Соединения схемы обратной связи соответствуют коэффициентам порождающего многочлена, который имеет  следующий вид [2, 3]

.  (1)

Процедура кодирования, использующее устройство, изображенное на рисунке 1 следующая:

При первых k  сдвигах ключ 1 закрыт для передачи битов сообщения в (n – k) – разрядный регистр сдвига. Ключ 2 установлен в нижнее положение для передачи битов сообщения на вы­ходной регистр в течение первых  k  сдвигов. После передачи k - гo бита сообщения ключ 1 открывается, а ключ 2 переходит в верхнее положение. При остальных n – k сдвигах происходит очищение кодирующих регистров, биты четности перемещаются на выходной регистр. Общее число сдвигов равно п, и содержимое выходного регистра представляет собой многочлен кодового слова .

Систематическое кодирование циклического кода

Закодируем вектор со­общения m = 1011 в кодовое слово (7, 4), используя регистр сдвига с обратной связью, показанный на рисунке 1. Порождающий многочлен равен g(X) = 1 + X + X3. Имеем  m = 1011, тогда 

.

Умножим m(Х) на .

.

Так как , то

по модулю .

Для 3 – разрядного регистра сдвига, показанного на рисунке 2, действия будут сле­дующими:


Входная очередь

Номер сдвига

Содержимое

регистра

Выход  и обратная связь

1011

0

000

-

101

1

110

1

10

2

101

1

1

3

100

0

–

4

100

1


Рисунок 2. Пример кодирования циклического (7, 4) кода  с по­мощью

(n – k) – разрядного регистра сдвига

После четвертого сдвига открывается ключ 1, ключ 2 переходит в верхнее положение, а би­ты четности переходят в выходной регистр. Получаем выходное кодовое слово  U = 1001011 или, в виде многочлена, [2, 4].

Обнаружение ошибок с помощью (n – k) – разрядного регистра сдвига

Передаваемое кодовое слово может быть искажено помехами, тогда при­нятый вектор будет искаженным вариантом переданного кодового слова. Пусть передается кодовое слово U(X), a принимается вектор Z(X). Каждый многочлен кодового слова в подпростран­стве имеет вид

,  (1)

где U(X) – многочлен степени п – 1 или меньше, а m(X) вектор сообщения в форме многочлена степени k – 1. Он имеет следующий вид:

.  (2)

Посколь­ку U(X) – это многочлен кодового слова, он должен без остатка делиться на порождающий многочлен  g(X). Представим Z(X), искаженную версию U(X), следующим образом:

,  (3)

где е(Х) – полином модели ошибки. Декодер начинает проверять, является ли Z(X) многочленом кодового слова, т. е. делится ли он на g(X) без остатка. Это осуществляется путем вычисления синдрома принятого многочлена. Синдром S(X) равен остатку от деления Z(X) на g(X):

,  (4)

где S(X) – полином степени п – k – 1 или меньше. Используя уравнения (3) и (4), получаем, что

.  (5)

Сравнивая уравнения (3) и (4), видно, что синдром S(X), полученный как Z(X) по модулю g(X), аналогичен остатку деления е(Х) на g(X). Таким образом, синдром приня­того многочлена Z(X) содержит информацию, необходимую для исправления модели ошибки. Расчет синдрома выполняется с помощью схемы деления, почти аналогичной схеме кодирования, используемой в передатчике. Пример вычисления синдрома со сдвигом на (n – k) разрядов регистра приведен на рисунке 3 с использованием вектора ко­да, полученного в нашем примере. В исходном состоянии ключ 1 закрыт, а ключ 2 открыт. Принятый вектор подается во входной регистр, в котором в исходном состоянии все разряды имеют нулевое значение. После того как весь принятый вектор будет занесен в регистр сдвига, содержимое регистра и есть синдром. Затем ключ 1 открывается, а ключ 2 закрывается, так что вектор синдрома теперь можно извлечь из регистра. Опи­санная последовательность действий имеет следующий вид.

Рисунок 3 – Вычисление синдрома с помощью (n – k) – разрядного

регистра сдвига


Входная очередь

Номер сдвига

Содержимое регистра

1001011

0

  00

100101

1

  100

10010

2

  110

1001

3

  011

100

4

  011

10

5

  111

1

6

  101

–

7

  000 – Синдром

Считается, что принятый вектор является правильным кодовым словом, если вектор синдрома нулевой. Если синдром отличен от нуля, тогда считается, что обнаружена ошибка и при­нятый вектор – это искаженное кодовое слово. Данная ошибка исправляется путем прибавления к принятому вектору вектора ошибки (указанной синдромом), т. е. аналогично процедуре, описанной в [1]. Этот метод декодирования хорош для простых кодов. Более сложные коды для практического использования требуют при­менения алгебраических методик.

СПИСОК ЛИТЕРАТУРЫ


Ташатов линейные блочные коды с контролем четности.  //  Вестник ПГУ им. . – 2007.  –  № 1  с. 123-135.  ифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – Издательский дом «Вильямс», 2004. – 1104 с. ил. сновы кодирования. Москва: Техносфера, 2004. – 288 с. , , Мощицкий информации (двоичные коды). Харьков, издательское объединение «Вища школа», 1978, 252 с.

Резюме

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