Основу оборудования,используемого при кодировании и исправлении или обнаружении ошибок с помощьюлинейных кодов(в том числе циклических),составляют линейные переключательные схемы с конечным числом состояий.
О П Р Е Д Е Л Е Н И Я .
Предполагается,что в линейных переключательных схемах информация представлена с помощью элементов поля GF(q).
Используется три вида устройств.
Первое из них - СУММАТОР,имеющий два входа и один выход,причём выходной символ равен сумме входных.
Второе - ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО с одним входом и одним выходом.
Оно может быть устройством задержки,выходной символ которого всегда совпадает с входным символом в предшиствующий момент времени.Его можно рассматривать также как ячейку регистра сдвига.В регистре сдвига имеется сигнал сдвига,не показанный на схемах,который приходит обычно со схемы синхронизации.В момент прихода этого сигнала выходной символ каждой ячейки принимает значение,которое было на входе непосредственно перед сигналом сдвига.
Третий вид устройств - это УСТРОЙСТВО УМНОЖЕНИЯ НА КОНСТАНТУ,имеющее один вход и один выход,причём выходной символ равен входному, умноженному на некоторую константу(которой может быть любой элемент поля).В этих устройствах любое число входов может быть соединено с любым выходом,но никакие два выхода не могут быть соединены.
Эти устройства изображаются так:
┌┴┐ ┌─┐
─>│+├─> ─>│a├─>
└─┘ └─┘
Линейными переключательными схемами с конечным числом состояний называются любые схемы,содержащие конечное число сумматоров,устройств памяти и устройств умножения на константу,соединённых любым допустимым способом.
Любая линейная переключательная схема (ЛПС) с конечным числом состояний может быть реализована при помощи логических элементов,используемых в ЦВМ.В бинарном случае (/* в поле GF(2) */) сумматор представляет собой логический элемент "ИСКЛЮЧАЮЩЕЕ ИЛИ",а устройство памяти является устройством задержки (D-триггер),либо ячейкой обычного двоичного регистра сдвига.Введение в схему умножителя на константу,равную 1,эквивалентно введению дополнительного соединения,а умножитель на константу,равную 0,соответствует отсутствию такого соединения.
Вход и выход предполагаются последовательными,т.е.входной сигнал состоит из элементов поля,подаваемых на входной конец последовательно - по одному в единицу времени;аналогичным образом формируется выходной сигнал.Когда,как это часто бывает,на входе или выходе появляется полином,то на входном или выходном конце имеются только коэффициенты,которые передаются НАЧИНАЯ С ВЫСШИХ ПОРЯДКОВ,потому что при делении у делимого сначала должныбыть обработаны коэффициенты высших порядков.Так,полином
f(X) = fnX^n + fn-1X^n-1 + ... + f0
будет подаваться на входной конец или появляться на выходном конце в виде последовательности из n элементов поля,которая будет начинаться с fn,через единицу времени появится fn-1,спустя ещё единицу времени появится fn-2 и т.д.
У М Н О Ж Е Н И Е И Д Е Л Е Н И Е П О Л И Н О М О В
П Р И П О М О Щ И Л П С .
У М Н О Ж Е Н И Е П О Л И Н О М О В .
Выход
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
┌── │+│───────────│+│─────│+│─...─────│+│───────│+│──────│+│───>
│ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘
│ └───┐ │ │ │ │ │
│ │ │ │ │ │ │
┌───┐ ┌────┐ ┌────┐ ┌────┐ ┌───┐ ┌───┐ ┌───┐
│ hr│ │hr-1│ │hr-2│ │hr-3│ │ h2│ │h1 │ │h0 │
└───┘ └────┘ └────┘ └────┘ └───┘ └───┘ └───┘
│ │ │ │ │ │ │
│ ┌───┐ │ ┌────┐ │ ┌────┐│ ┌──────┐│┌──────┐│┌──────┐│
─>─┴──│ ai│─┴─ │ai+1│─┴─│ai+2│┴...─│ai+r-3│┴│ai+r-2│┴│ai+r-1│┘
Вход └───┘ └────┘ └────┘ └──────┘ └──────┘ └──────┘
Рис. П П 1 .
Изображённая схема используется для умножения любого полинома на входе
a(X) = akX^k + ak-1X^k-1 + ... + a1X + a0
на фиксированный полиом
h(X) = hrX^r + hr-1X^r-1 + ... +h1X + h^0 .
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.