Построение кодирования

Кодирование строится на основе следующих принципов и понятий:

1) Кодовое слово. Кадр или сообщение состоит из m информационных битов и k избыточных (или контрольных). Полная длина кадра n = m+k. Набор из n бит называют n-битным кодовым словом или кодовой комбинацией.

2) Кодовое расстояние. Количество битов, которыми различаются 2 кодовых слова. Для получения кодового расстояния между кодовыми словами их надо сложить по модулю 2 и сосчитать количество единиц. Например, 1000101 – первое кодовое слово, и 1011001 – второе. Результат – 0011100. Кодовое расстояние равно 3. Смысл кодового расстояния заключается в следующем. Если 2 кодовых слова находятся на кодовом расстоянии t, то для преобразования одного кодового слова в другое потребуется d единичных ошибок. Если кодовое слово длиной m+k, то 2^m – количество допустимых комбинаций (информационных сообщений). Не все допустимые информационные сообщения при появлении ошибок будут входить в 2ⁿ число сообщений. При этом контрольные разряды формируются по определённому алгоритму. Зная алгоритм формирования контрольных разрядов, можно построить полный список всех допустимых кодовых слов. При этом в этом списке можно найти такую пару кодовых слов, кодовое расстояние между которыми будет минимальным. Это расстояние называется минимальным кодовым расстоянием. Обычно обозначается d_min. Способность алгоритма кодирования по обнаружению и исправлению ошибок зависит от минимального кодового расстояния.

Вывод:

Не все значения кодовых слов 2^n=m+k являются допустимыми.

Пример обнаружения ошибки: применяют кодирование с контрольным разрядом или контроль на чётность. Бит чётности формируется таким образом, чтобы количество единиц в кодовом слове было чётным.

10110101 – m информационных бит, 1 – k контрольных бит. Минимальное кодовое расстояние равно d_min=2. При приёме осуществляется подсчёт единиц и сравнение полученной суммы с контрольным разрядом. Если количество единиц нечётное, то произошла ошибка. Где – неясно.

Исправление ошибки: Предположим. Допустимые комбинации следующие:

1) 0 0 0 0 0 0 0 0 0 0

2) 0 0 0 0 0 1 1 1 1 1

3) 1 1 1 1 1 0 0 0 0 0

4) 1 1 1 1 1 1 1 1 1 1

d_min = 5. Если получено сообщение R = 0000000111 – ошибка, такого допустимого кодового слова нет, количество исправленных ошибок подсчитывается по формуле . Поэтому на приемном конце будет сделан вывод о том, что передавалось 0000011111. Но возможен вариант, когда передавались 00…00 и произошла тройная ошибка, тогда исправление будет неверным – ошибка декодирования.

Пример: код с обнаружением ошибки. Полиноминальный код CRC (Cyclic Redundancy Check).

В основе – представление битовых строк кадра в виде многочленов с коэффициентами 0 и 1. Кадр из k бит рассматривается как список коэффициентов многочлена вида X^k-1 + X^k-2 + … + X⁰, где X принимает значения 0 или 1 в зависимости от значения в разряде. Например 1 1 0 0 0 1 соответствует X⁵ + X⁴ + X⁰

При исполнении циклического кода источник и адресат договариваются об образующем многочлене G(X), а точнее его степени.

Идея – добавление избыточности (контрольной суммы) в конец кадра таким образом, что бы получающееся кодовое слово на приемном конце делилось на многочлен G(X) без остатка. Приемник пытается разделить его на G(X), ненулевой остаток означает ошибку.

Последовательность вычисления контрольной суммы следующая:

1. Пусть r – степень многочлена G. К информационному слову из n разрядов добавляется r нулевых битов.
2. Полученное кодовое слово (битовая строка) делится на G.
3. Остаток от деления вычитается из кодового слова. Результат – передаваемый кадр.

Примечание – перенос при сложении или вычитании не производится.

Пример:

1101011011, многочлен G = 10011

1. 1101011011 0000

. . . 01110 – остаток

_11010110110000

- передаваемый кадр.

1. На приемнике

. . . 0 - остаток

Если есть остаток – есть ошибки.

Данный метод используется в стандарте IEEE 802х, с многочленом 32й степени.

Пример кода исправления ошибки – код Хемминга.

При кодировании биты информационного слова (и кодового) нумеруются последовательно слева на право, начиная с первого. Кодовое слово из информационного строится таким образом, чтобы с номерами кратными 2м являлись контрольными (1,2,4,8,16).

Пример:

01 1 0 0 1 0 0 0 0 – кодовое слово, подчеркнутые – контр.

1 0 1 0 0 0 – инф слово.

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

В коде Хемминга контрольный бит n стоит на месте 2ⁿ

r₁ r₂ r₃ r₄

1 2 3 4 5 6 7 8

r₁ – сумма разрядов 3, 5, 7, 9, 11…

r₂ – сумма разрядов 3, 6, 7, 10, 11, 14…

r₃ – сумма разрядов 5, 6, 7, 12, 13, 14, 15…

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

Пример

Пусть необходимо передать сообщение 1011

--1-011

Необходимо закодировать сообщение таким образом, чтобы в случае ошибки найти, какой бит инвертирован.

r₁ = 0 – 3, 5 и 7-й биты

r₂ = 1 – 3, 6 и 7-й биты

r₃ = 0 – 5, 6 и 7-й

Полностью закодированное сообщение: 0110011

Для подсчета без ошибок:

S₁ = r₁ + 3 + 5 + 7 + …

S₂ = r₂ + 3 + 6 + 7 + …

S₃ = r₃ + 5 + 6 + 7 + …

S₁ = S₂ = S₃ = 0 => ошибок нет

Если S₃, S₂, S₁!= 0, то расположение битов показывает, в каком разряде инвертирован бит.

Дата добавления: 2015-07-11