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

═══════════════════════════════════════════════════════════════════

Первые шесть сдвигов не имеют аналогий при делении "столбиком".После шестого сдвига содержимое регистра сдвига соответствует полиному,обозначенному буквой А.Его старший коэффициент равен первому символу частного и,кроме того,выходу после седьмого сдвига.Обратной связи соответствует полином,обозначенный через В,а входу - одночлен

С,сносимый вниз при делении столбиком.После седьмого сдвига содержимому регистра сдвига соответствует полином,обозначенный буквой D.

Обратная связь даёт полином E;одночлен F,сносимый вниз,совпадает с входным символом;после восьмого сдвига содержимым регистра является многочлен G.

Этот процесс продолжается до тех пор,пока после 14 сдвигов,по одному для каждого коэффициента делимого,содержимым регистра не станет остаток от деления и все коэффициенты частного не появятся на выходе.

В этой схеме коэффициент при X^j в частном появляется на выходе в тот же момент времени,когда коэффициент при X^j появляется на входе.Таким образом,вход и частное синхронны.

У М Н О Ж Е Н И Е  -  Д Е Л Е Н И Е   П О Л И Н О М О В .

┌───────┬────────┬─────<──<─────┬───────┬─────>

┌───┐   ┌───┐    ┌───┐         ┌─────┐┌─────┐

│-g0│   │-g1│    │-g2│         │-gr-1││gr^-1│

└───┘   └───┘    └───┘         └─────┘└─────┘

│       │        │             │        │

┌─┐ ┌─┐ ┌─┐ ┌──┐ ┌─┐ ┌──┐      ┌─┐ ┌──┐ ┌─┐

│+│─│ │─│+│─│  │─│+│─│  │─>.. ─│+│─│  │─│+│

└─┘ └─┘ └─┘ └──┘ └─┘ └──┘      └─┘ └──┘ └─┘

│       │        │             │        │

┌──┐    ┌───┐    ┌───┐         ┌────┐   ┌───┐

│h0│    │h1 │    │h2 │         │hr-1│   │hr │

└──┘    └───┘    └───┘         └────┘   └───┘

─────────┴───────┴────────┴─────────────┴────────┴─────>

Вход

Рис.ПДП.

Схема регистра сдвига,с помощью которой может производиться сначала умножение на полином h(X),а затем деление на полином g(X),изображена на рис.ПДП.Как видно из рисунка,она получается комбинированием схемы умножения (рис.ПП2) и схемы деления (рис.ДП).Здесь предполагается,что степень многочлена h(X) не превосходит степени многочлена g(X).

ПРИМЕР.На рисунке показана схема регистра сдвига (РС),используемого для умножения входного полинома на полином X^5 + X + 1 и для деления результата на полином X^6 + X^5 + X^4 + X^3 + 1.

┌──────────────────────┬────────┬────────┬───────┐

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

│+│─│  │─│+│─│  │─│  │─│+│─│  │─│+│─│  │─│+│─│  │─┴──────>

└─┘ └──┘ └─┘ └──┘ └──┘ └─┘ └──┘ └─┘ └──┘ └─┘ └──┘

──>──┴────────┴───────────────────────────────┘

Вход

Если постоянный множитель имеет степень,более высокую,чем делитель, то в конце РС,соответствующем членам низшего порядка,должны быть помещены дополнительные ячейки.В этом случае,для того,чтобы закончить деление,требуется произвести столько же дополнительных сдвигов с нулём на входе,сколько ячеек было добавлено.Например,схема умножения входного полинома на полином X^10 + X^9 + X^5 + 1 и деления получившегося произведения на многочлен X^6 + X^5 + X^4 + X^3 + 1

имеет вид

┌───────────────────┬───────┬───────┬───────┬──>

┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐

┌│ │─│ │─│ │─│ │─│+│─│ │─│+│─│ │─│ │─│+│─│ │─│+│─│ │─│+│─│ │─│+│

│└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘

─┴───────────────>─────────┴───────────────────────────>───────┘

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

Г Е Н Е Р А Т О Р   Р Е Г И С Т Р А   С Д В И Г А

С   Л И Н Е Й Н О Й   О Б Р А Т Н О Й   С В Я З Ь Ю .

Выше мы рассмотрели два способа построения циклических кодов.Согласно 1-му способу кодовая комбинация Pn,k кода получается следующим образом.Исходная комбинация A(X),deg A(X)<=k,умножается на X^p,где

p=deg K(X),определяется остаток R(X) от деления A(X)*X^p на K(X).

Кодовая комбинация F(X) = A(X)*X^p+R(X).