Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 28

Как видно из таблицы,в случае а)получаем последовательность,которая соответствует первой строке матрицы P7,4,а в случае б) по-разрядной сумме по модулю два первой и второй строки матрицы P7,4,т.е.

обе последовательности являются кодовыми комбинациями P7,4 - циклического кода.

М Е Т О Д Ы   К О Д И Р О В А Н И Я .

Наиболее важная особенность циклических кодов - простота их реализации.

В зависимости от способа построения циклического кода различают два способа их кодирования.В обоих методах кодирования предполагается,что из источника поступают блоки из k информационных символов, которые потом без задержки попадают в канал.После этого посылаются следующие за каждым таким блоком p = n-k проверочных символов;в течение этого времени никакая информация из источника приннята быть не может.Таким образом,в обоих методах предполагается наличие источника,способного по команде начинать и прекращать выдачу символов, или же использование буферного устройства.

Ниже описывается два способа сопоставления информационному набору из k символов кодового слова циклического кода.При первом способе используется регистр сдвига с k ячейками,при втором - регистр сдвига с n-k ячейками.Для кодов,число проверочных символов в которых больше числа информационных символов,вообще говоря,предпочтительнее первый способ,тогда как для кодов,в которых k/n > 0.5,второй способ оказывается обычно более экономичным.Оба способа порождают одни и те же кодовые слова.

П Е Р В Ы Й   М Е Т О Д   К О Д И Р О В А Н И Я .

Кодирование для циклического (n,k) - кода,порождённого полиномом

K(X) степени p=n-k,может быть произведено с помощью регистра сдвига с k ячейками (рис.генератор регистра сдвига),соединения в котором соответствуют проверочному полиному H(X) = (X^n + 1)/K(X).Сначала информационные символы помещаются в эти k ячеек,затем производится

n сдвигов.Первые k символов,появившихся на выходе,будут информационными,а последние n-k символов - проверочными.Вместе они образуют кодовый вектор длины n.

ПРИМЕР.Пример кодирования фактически уже рассмотрен при анализе работы генератора регистра сдвига.Для P7,4 циклического кода с образующим полиномом K(X) кодер имеет вид ( K(X) = X^3 + X^3 + 1):

┌─┐     ┌─┐

┌────│+│<────│+│<───────────┐

│    └─┘     └─┘            │

Вход    │ ┌──┐ │ ┌──┐ │ ┌──┐   ┌──┐ │ Выход

───── \─┴─│r0│─┴>│r1│─┴>│r2│──>│r3│─┴────>

^   └──┘   └──┘   └──┘   └──┘

Вниз на первых 4-х тактах

Вверх на последующих 7-и тактах

В результате первых 4-х сдвигов информационные символы будут помещены в регистр сдвига.На последующих 7-и тактах на выходе появится кодовая комбинация циклического кода.

В Т О Р О Й   М Е Т О Д   К О Д И Р О В А Н И Я .

Теперь рассмотрим кодирование при помощи регистра сдвига с n-k=p

ячейками.Кодовое слово может быть найдено как результат умножения полинома степени k-1 или меньше,коэффициентами которого являются произвольные информационные символы,на K(X) - порождающий многочлен кода.Умножение можно осуществить,используя линейную схему,изображённую на рис.ПП1,или схему,представленную на рис.ПП2.При таком методе кодирования информационные символы появляются в кодовом полиноме в изменённом виде,однако они могут быть восстановлены по НЕИСКАЖЁННОМУ КОДОВОМУ ПОЛИНОМУ путём деления его на полином K(X).Для деления можно использовать схему,изображённую на рис.ДП.

ПРИМЕР: см.методы декодирования.

Т Р Е Т И Й   М Е Т О Д   К О Д И Р О В А Н И Я .

В большинстве случаев значительно удобнее,чтобы кодовый вектор состоял из k неизменённых информационных символов,за которыми следуют

n-k проверочных символов.Любой циклический код может быть представлен в таком виде при построении его согласно 1-му способу образования циклического кода.Кодовое слово при этом представляется в следующем виде

F(X) = Q(X)K(X) = A(X)X^p + R(X), где  F(X) - кодовая комбинация;

Q(X) - частное от деления полинома A(X)X^p на полином K(X);

K(X) - образующий полином;

A(X) - полином исходных k информационных символов;

R(X) - остаток от деления A(X)*X^p на K(X).