УДК 004

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

Лобач Ия Кирилловна – студент Санкт-Петербургского государственного университета аэрокосмического приборостроения.

Аннотация: Данная статья рассматривает моделирование работы типового алгоритма формирования контрольной суммы для обнаружения ошибок при передаче данных. Будет описан алгоритм кодирования исходного сообщения, а также два способа декодирования принятого сообщения. Будет доказана эквивалентность двух вариантов работы декодера. В статье также будут приведены результаты моделирования работы кодера и каждого из вариантов декодера, в результате которых можно будет убедиться в эквивалентности принимаемых решений о наличии ошибки при передаче данных по каналу. Она будет полезна для всех тех, кто интересуется системами передачи данных.

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

Введение

Исследуемую систему можно описать следующим образом: к данным, которые необходимо передать, добавляется контрольная сумма (КС), вычисляемая по типовому алгоритму. При получении сообщения значением контрольной суммы проверятся и принимается решение о том, возникли ли ошибки при передаче по каналу или нет. Описанную схему можно представить рисунком 1:

1

Рисунок 1. Передача данных.

Передается некоторое двоичное сообщение m. В кодере к этому сообщению считается контрольная сумма. Тогда передаваемое сообщение a (кодовое слово) будет состоять из m и контрольной суммы. Это сообщение передается по каналу, где могу произойти ошибки e В данной работе канал будет описан следующим образом: бит сообщения, где произошла ошибка, инвертируется. Таким образом, после передачи по каналу декодер принимает последовательность b и проверяет КС полученного сообщения, после чего принимает решение.

Кодер

Для описания работы с двоичными кодами используются многочлены с коэффициентами из GF(2). Кодер хранит порождающий многочлен g(x). Степень многочлена deg(g(x)) = r определяет количество бит контрольной суммы. k – количество бит передаваемого сообщения m. Кодером выполняются следующие шаги:

  • По m формируется многочлен m(x), степень которого deg(m(x)) ≤ k −1;
  • c(x) = m(x)x r mod g(x), причем его степень deg(c(x)) ≤ r − 1;
  • a(x) = m(x)x r + c(x), причем его степень deg(a(x)) ≤ k + r − 1;
  • По a(x) формируется последовательность a, причем ее длина n = k + r.

Декодер

Декодер также хранит порождающий многочлен g(x) и выполняется следующие шаги:

  • Принимаемое b = a + e преобразуется в многочлен b(x);
  • s(x) = b(x) mod g(x) (синдром);
  • Если синдром равен 0, то считается, что ошибок не было E = 0, в противном случае E = 1.

Существует альтернативная реализация декодера, выполняющего следующие шаги:

  • Принимаемое b = a + e состоит из m длины k и КС c длины r;
  • m подается на вход кодеру и вычисляется новая КС c′;
  • Если c′ = c, то считается, что ошибок не было E = 0, в противном случае E = 1.

Моделирующая программа. Описание в виде блок-схем

Моделирующую программу можно разделить на четыре части. Описание каждой из них будет представлено в виде блок-схем на рисунке 2-5:

2

Рисунок 2. Блок-схема для ввода данных.

3

Рисунок 3. Блок-схема для кодера.

4

Рисунок 4. Блок-схема декодера.

5

Рисунок 5. Блок-схема альтернативного декодера.

Описание результатов проводимых исследований

Моделирующая программа показала, что результаты, полученные типовым алгоритмом декодирования и альтернативным всегда совпадают, т.е., если ошибка была обнаружены первым декодером, то и второй ее обнаружит, в противном случае оба декодера примут неверное решение. На вход декодерам подается b = a + e. Как видно, на результат декодирования влияет произошедшая в канале ошибка e. Тогда, чтобы проверить результаты работы 2 декодеров зафиксируем кодовое слова a и переберем всевозможные векторы ошибки e. Пусть порождающий многочлен g(x) и кодовое слово a имеют вид, представленный на рисунке 6:

6

Рисунок 6. Исходные данные.

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

7

Рисунок 7. Результаты работы двух вариантов декодера.

Результаты работы 2 декодеров всегда совпадут. Это объясняется следующим образом. Пусть на вход декодерам подается один и тот же вектор b(x), также оба декодера используют одинаковый порождающий многочлен g(x). Доказательство будет строится от противного, а именно, пусть декодеры примут разное решение: первый декодер не найдет ошибку, а второй найдет. Пусть первый декодер примет решение, что ошибки не было, т.е. посчитанный им синдром s(x) будет равен 0:

s(x) = 0 = b(x) = a(x) + e(x) mod g(x)

Известно, что, как и кодовое слово, b(x) состоит из k бит информационной части и r бит, относящихся к КС. Пусть пришедшая на вход декодеру информационную часть будет обозначена, как m'(x), а КС как c'(x). Тогда можно записать так: a(x) + e(x) = m'(x)xr + c'(x) = 0 mod g(x). Тогда: m'(x)xr + c'(x) = 0 mod g(x).

Важно отметить, что альтернативных декодер принимает решение путем сравнения двух КС. За первую КС принимается та, которая приходит ему на вход, т.е. c'(x), а с помощью кодера формируется еще одна КС, которую обозначим как c''(x).

Альтернативный декодер по нашему предположению принимает решение, что КС c'(x) и c′′(x) не совпадают, т.е. c′(x) ≠ c′′(x).

Теперь подробнее будет рассмотрена КС c′′(x). Она формируется путем кодирования информационной части m′(x). Тогда, ее можно записать, как: c′′(x) = m′(x)x rmod g(x)

Объединяя все полученные выражения, получено:

c ′(x) ≠ c ′′ (x) ⇒ m′ (x)x r ≠ m′ (x)x r mod g(x)

Очевидно, что такая ситуация невозможна, а, значит, результаты декодеров всегда совпадут.

Заключение

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

Список литературы

  1. Тюрликов А. М., Бурков А. А., Основы построения инфокоммуникационных систем и сетей: лабораторный практикум / СПб.: ГУАП, 2018. 4 с.
  2. Марковский С. Г. Элементы теории помехоустойчивого кодирования: учебное пособие / С. Г. Марковский, А. М. Тюрликов. СПб.: ГУАП, 2014. 95 с.
  3. Колесник В. Д. Кодирование при передаче и хранении информации (Алгебраическая теория блоковых кодов): учебное пособие для студентов высших учебных заведений / В. Д. Колесник. М.: Высшая школа, 2009. 549 с.
  4. Кудряшов Б. Д. Основы теории кодирования: учебное пособие для студентов высших учебных заведений / Б. Д. Кудряшов. СПб.: БХВ-Петербург, 2016. 393 с.
  5. Финк Л. М. Теория передачи дискретных сообщений / Л. М. Финк. М.: Советское радио, 1970. 728 с.

Интересная статья? Поделись ей с другими: