Sn8
2.
Циклические коды
2.1 Общее
представление циклических кодов
Основные свойства циклического кода и способы построения.
Циклические коды получили довольно широкое применение благодаря их
эффективности при обнаружении и исправлении ошибок. Схемы кодирующих и
декодирующих устройств для этих кодов чрезвычайно просты и строятся на основе
обычных регистров сдвига.
Название кодов произошло от их свойства, заключающегося в
том, что каждая кодовая комбинация может быть получена путем циклической
перестановки символов комбинации, принадлежащей к этому же коду. Это значит,
что если, например, комбинация a0 a1 a2. an-1 является разрешенной
комбинацией циклического кода, то комбинация an-1 a0 a1 a2 …an-2 также принадлежит этому
коду.
Циклические коды удобно рассматривать, представляя комбинацию
двоичного кода не в виде последовательностей нулей и единиц, а в виде полинома
от фиктивной переменной x, а именно;
G (x) = an-1 xn-1
+ an-2 xn-2 +…+ a1 x + a0, (1)
где ai - цифры данной системы
счисления (в двоичной системе 0 и 1). Так, например, двоичное семиразрядное
число 1010101 может быть записано в виде полинома
σ (x) = 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 0x1 + 1x0 = x 6 + x 4 + x 2+ 1. (2)
Наибольшая степень x в слагаемой с ненулевым
коэффициентом называется степенью полинома.
Представление кодовых комбинаций в форме (2) позволяет свести
действия над комбинациями к действию над многочленами. При этом сложение
двоичных многочленов сводится к сложению по модулю два коэффициентов при равных
степенях переменной x; умножение производится по обычному правилу
перемножения степенных функций, однако полученные при этом коэффициенты при
равных степенях переменной x складываются по модулю два; деление
осуществляется по правилам деления степенных функций, при этом операции
вычитания заменяются операциями суммирования по модулю два.
Представление комбинаций в формах (1) и (2) удобно еще и тем,
что упомянутая ранее циклическая перестановка есть результат простого умножения
данного полинома на х. Действительно, если одна из кодовых комбинаций
выражается полиномом V (x) = a0 + a1 x + a2 x2 +…+ an-2 xn-1+ an-1 xn-1, то
новая комбинация за счет циклического сдвига будет x V (x) = a0 x + a1 x2 + a2 x3 +…+ an-1 xn. Однако в последнем члене
необходимо заменить xn на 1. Следовательно,
новая комбинация будет
V1 (x) = a0
x + a1 x2 + a2 x3 +…+
an-2 xn-1.
Например, циклический сдвиг кодовой комбинации 1010101 может
быть получен путем умножения полинома (2) на x
G (x) х = x7 + x5 + x3 + x.
Заменив х7 на 1, получим полином
G1 (x) = x5 + x3 + x3 + 1, соответствующий кодовой
комбинации 0101011.
Согласно определению циклического кода для построения
производящей матрицы Pn,k достаточно выбрать только
одну исходную n - разрядную комбинацию V1 (x). Циклическим сдвигом можно
получить (n - 1) различных комбинаций, из которых любые k комбинаций могут быть
взяты в качестве исходных. Суммируя строки производящей матрицы во всех
возможных комбинациях, можно получить остальные кодовые комбинации. Можно
показать, что кодовые комбинации, получаемые из некоторой комбинации V1 (x) циклическим сдвигом,
удовлетворяют условиям, предъявляемым к совокупности исходных комбинаций.
Циклический сдвиг комбинации с единицей в старшем n-м разряде
равносилен умножению соответствующего многочлена на x с одновременным
вычитанием из результата многочлена (хп - 1) или (хп +1),
так как операции осуществляются по модулю два. Следовательно, если в
качестве исходного взять некоторый полином Р (х), то процесс получения
базовых полиномов можно представить в следующем виде:
U1 (x) = P (x)2
(x) = P (x) x - C2 (xn + 1);
U3 (x) = P (x)
x2 - C3 (xn + 1); (3)
......
Un (x) = P (x)
xn-1 - Cn (xn + 1),
где С2, С3,. Сn - коэффициенты, принимающие
значение 1 при Р (х) хi ≥ (хп -
1) и
значение 0 при Р (х) xi < (хп - 1).
При таком способе построения базовых полиномов полином Р
(х) называют образующим.
Если принять условие, что полином Р (х) является
делителем двучлена (хп +1), то базовые комбинации, а вместе с
ними и все разрешенные комбинации кода приобретают свойство делимости на Р
(х). Из этого следует, что принадлежность кодовой комбинации к группе
разрешенных можно легко проверить делением ее полинома на образующий полином Р
(х). Если остаток от деления равен нулю, то комбинация является
разрешенной.
Это свойство циклического кода используется для обнаружения
или исправления ошибок. Действительно, если под воздействием помех разрешенная
кодовая комбинация трансформируется В запрещенную, то ошибка может быть
обнаружена по наличию остатка при делении комбинации на образующий полином Р
(х).
Таким образом, образующий полином Р (х) должен
удовлетворять требованию - он должен быть делителем двучлена (хп +1).
Выбор Р (х) однозначно определяет циклический код и его корректирующие
свойства.
Циклический (n,k) - код может быть
получен путем умножения простого k-значного кода, выраженного в виде полинома
степени (k - 1), на некоторый образующий полином Р (х) степени (n - k).
Возможна и другая процедура получения циклического кода. Для
этого кодовая комбинация простого k-значного кода G (х) умножается на одночлен xn-k, а затем делится на
образующий полином Р (х) степени (n - k). В результате умножения G (х) на xn-k степень каждого
одночлена, входящего в G (х), повысится на (n - k). При делении произведения xn-k G (x) на образующий полином Р
(х) получится частное Q (х) такой же степени, как и G (х).
Результат умножения и деления можно представить в следующем
виде:
xn-k G (х) / Р (х) = Q (х) + R (х) / Р (х), (4)
где R (х) - остаток от деления xn-k G (х) на Р (х).
Так как частное Q (х) имеет такую же степень, как и кодовая
комбинация G (х), то Q (х) также является комбинацией простого k-значного кода.
Умножая обе части равенства (4) на Р (х) и произведя
некоторые перестановки, получим
F (x) = Q (х) Р (х) = xn-k G (х) + R (х). (5)
В правой части (5) знак минус перед R (х) заменен знаком плюс, так
как вычитание по модулю два сводится к сложению.
Таким образом, кодовая комбинация циклического (n,k) - кода может быть
получена двумя способами:
· путем умножения простой
кодовой комбинации степени (k - 1) на одночлен xn-k и добавления к этому
произведению остатка, полученного от деления полученного произведения на
образующий полином Р (х) степени (n - k);
· путем умножения простой
кодовой комбинации степени (k - 1) на образующий полином Р (х) степени (n - к).
При первом способе кодирования первые k символов полученной
кодовой комбинации совпадают с соответствующими символами исходной простой
кодовой комбинации.
При втором способе в полученной кодовой комбинации
информационные символы не всегда совпадают с символами исходной простой
комбинации. Такой способ легко реализуем, но вследствие того, что в полученных
кодовых комбинациях не содержатся информационные символы в явном виде, усложняется
процесс декодирования.
В связи с вышеизложенным на практике обычно используется
первый способ получения циклического кода.
2.2
Кодирование циклических кодов
Как было показано, комбинация циклического кода имеет вид
многочлена f (x) =g (x) q (x) =xn-m u (x) +r (x). При передаче такой
комбинации по каналу связи на приемной стороне получена комбинация p (x). При наличии ошибок
многочлен p (x), вообще говоря, не делится на g (x), чем и обнаруживается
наличие ошибок.
Пример. Пусть и (x) =1+ x2+ x3+ x7+ x9=1011000101, g (x) =1+ х2+ x4+ x5=101011, тогда xn-m = х5 и xn-m u (x) = x5+ x7+ x8+ x12+ x14= 000001011000101.
Произведем деление xn-m u (x) на g (x). В результате деления
получим частное q (х) = 110101011 и остаток r=01110 (напомним, что деление начинается
со старших разрядов). Кодовый многочлен имеет следующий вид:
xn-m u (x) +r (x) = x+ x2+ x3+ x5+ x7+ x8+ x14=01110 1011000101.
Предположим, что многочлен ошибок e=110101100000000, тогда будет принят
многочлен р=101000111000101. Если р (х) разделить на g=101011, то получится остаток S (x) = 1, чем обнаруживается
наличие ошибки в принятой кодовой комбинации.
Остаток S (x) от деления р (х) на
g (х) называется синдромом. Так
как S (x) =p (x) + g (x) e (x), то синдром S (x) равен остатку от деления
многочлена ошибок е (х) на g (x). Таким образом, синдром,
вычисленный по принятому многочлену р (х), содержит информацию о векторе
ошибок. Исправление ошибок производится в следующей последовательности:
а) р (х) делится на g (x), получается остаток
(синдром) S (x);
б) по S (x) находится е (х);
в) сложением р (x) + е (х) получается f ´ (x).
Вычисление синдрома может быть реализовано на регистрах с
логической обратной связью - синхронных устройствах, состоящих из связанных
между собой элементов задержки и логических элементов. Вычисление синдрома
осуществляется подачей коэффициентов многочлена на регистр, начиная со старших
разрядов.
Кодирование циклического кода сводится к умножению исходной
комбинации u (х) на хп-т и прибавлению к ней остатка r (x) от деления хп-ти
(х) на g (x). При декодировании
вычисляется синдром S (x) путем деления р (x) на g (x). Поскольку операция
умножения многочлена на хп-т означает добавление к этому
многочлену (п-т) нулей, то никакого специального устройства для этого не
требуется. Деление многочлена на многочлен заключается в последовательном
сложении по модулю 2 делителя со старшими степенями делимого, затем со старшими
степенями получившегося остатка до тех пор, пока степень остатка не станет
меньше степени делителя (сложение по модулю 2 совпадает с вычитанием).
Деление произвольного многочлена на порождающий многочлен g (х) степени (n-т) может быть осуществлено
регистром с числом ячеек (n-т) и числом сумматоров, на единицу меньшим числа
ненулевых членов g (x). Место включения сумматоров определяется
структурой делителя g (x). Так, например, для g (x) =1+ х2+ x4+ x5 схема приведена не рис.4.
Рис. 4.
На вход регистра поступает последовательность разрядов,
начиная с высшего, многочлена-делимого. Как только первый разряд этой
последовательности появляется на выходе, происходит суммирование по модулю 2
делителя и первых разрядов делимого, а в элементах памяти записывается остаток.
Затем при появлении на выходе первой единицы остатка производится суммирование
делителя с этим остатком и т.д. После записи в ячейки памяти последнего разряда
делимого в них получается окончательный остаток. Операция деления занимает п
+1 тактов, где n - степень делимого. Последовательность работы схемы
рис.4. представлена в таблице ниже.
На основе рассмотренного регистра с логической обратной
связью может быть построено кодирующее устройство циклического кода (рис.5).
Рис. 5.
В течение первых (n
- m) тактов символы заполняют линию задержки ЛЗ и запоминающие
элементы, затем в течение последующих (m + 1) тактов происходит деление
(при этом ключ кл. k1 замкнут, а кл. k2 разомкнут) и на выход регистра
поступают все m информационных разрядов. В запоминающих
элементах остается остаток r (x). После этого кл. k2 замыкается, а кл.
k1 размыкается, и на выход регистра поступает остаток r (x), а ЛЗ и
элементы памяти заполняются (n - m) разрядами следующей комбинация и весь цикл повторяется. В
результате на выходе сначала последовательно появляются все m информационных, а затем (n - m) проверочных
разрядов n - разрядной кодовой комбинации.
Недостаток схемы рис. 5, заключающийся в необходимости задержки
информации на (n-m) тактов,
может быть устранен при использовании эквивалентной схемы рис. 6.
Рис. 6.
Сложность циклического кодера пропорциональна длине кода n.
Следовательно, кодер циклического кода намного проще, чем кодер произвольного
линейного кода, сложность которого пропорциональна n2.
2.3
Структурная схема мультиплексора Е1
3. Разработка
блока Формирователь CRC-4
Требуется спроектировать блок "Формирователь
CRC-4", который производит расчет суммы CRC-4 и включает результат в
сигнал следующего подсверхцикла. В блок входит кодер, регистр, мультиплексор и
устройство управления. В работе данного блока используются метки циклов. Схема
работы формирователя CRC-4 показана на Рис. 1.
Поток Е1 проходит через кодер, из первых 8 циклов берутся первые
биты TS0 и обсчитывает их по полиному Х4 +Х+1
и вставляет в следующие 8 циклов.
На Рис. 2. приведена общая структура разрабатываемого блока.
Рис. 2. Функциональная схема формирователя CRC-4.
Устройство управления выделяет метки циклов. Как только прошла
первая метка устройство управления дает команду кодеру начинать работу, при
прохождении девятой метки устройство управления выдает команду заканчивать
деление и вставлять просчитанные биты С1, С2, С3, С4 в следующие 8 циклов.
В устройство управления входят 2 счетчика последовательного типа с
непосредственными связями, схема которого представлена на Рис.3.
Перед поступлением счетных импульсов все разряды счетчика
устанавливаются в состояние "0" подачей импульса на вход
"Установка нуля". При поступлении первого счетного импульса первый
Т-триггер подготавливается к переключению в противоположное состояние, и после
окончания действия импульса переходит в состояние Q =1. В счетчик записывается число 1. Уровень 1 с выхода Q1 воздействует на счетный вход второго разряда, подготавливая его к
переключению.
По окончании второго счетного импульса первый Т-триггер переходит
в состояние "0", а второй Т-триггер переключается в состояние
"1". Таким образом, осуществляется работа счетчика с приходом
последующих импульсов.
Первый разряд счетчика переключается с приходом каждого входного
импульса, второй разряд - каждого второго, третий - каждого четвертого, а четвертый
срабатывает на каждый восьмой счетный импульс.
По окончании 15-го импульса все разряды счетчика устанавливаются в
состояние "1", а 16-й импульс переключает первый разряд счетчика в
состояние"0", следом за ним переключаются и остальные разряды в исходное
состояние. На Рис. 4. приведена временная диаграмма двоичного счетчика.
Схема счетчика выполнена на счетных Т-триггерах с внутренней
задержкой.
Характерным свойством Т-триггера является его переключение в
противоположное состояние с приходом каждого очередного входного импульса. В
выбранном Т-триггере особенностью является наличие дополнительного инвертора.
Последовательность переключения асинхронных R-S-триггеров, входящих в
Т-триггер: на этапе фронта входного импульса переключается основной триггер, а
по окончании длительности входного импульса - вспомогательный триггер. Этот
вариант Т-триггера называется также триггер с внутренней задержкой. На
Рис. 6. приведена временная диаграмма Т-триггера.
На Рис. 7. приведена схема разрабатываемого кодера.
На вход схемы поступают m информационных символов. В
течение первых m тактов замкнут кл. К1 и разомкнут кл. К2. При этом на выход
регистра поступает m информационных разрядов и одновременно производится
деление. Затем кл. К1 размыкается, а кл. К2 замыкается, и в течение последующих
(n-m) тактов на вход регистра ничего не подается, а на выход поступает остаток
от деления. По окончании передачи n - разрядной комбинации ключи возвращаются в
первоначальное положение и цикл повторяется. На Рис. 8. приведена временная
диаграмма кодера.
В кодер входят D-триггеры и логические элементы ИЛИ, выполняющие
операцию сложения по модулю два. На Рис. 10. приведена структурная схема
однотактного D-триггера. Их обозначение обусловлено свойством сохранять
состояние логической "1" после снятия входного сигнала до прихода
очередного тактового импульса. на Рис. 11. временная диаграмма D-триггера.
Остаток от деления из кодера попадает в последовательный регистр.
Из сдвигового регистра через параллельные выходы биты CRC-4 переходят в регистр памяти и регистр сдвига снова готов к
работе. На Рис. 12. приведена схема сдвигового регистра.
В параллельных регистрах запись двоичного числа осуществляется во
все разряды одновременно. Их функция сводится только к приему, хранению и
передаче информации. В связи с этим параллельные регистры часто называют регистрами
памяти. перед записью двоичного числа все триггеры устанавливаются в состояние
"0" подачей импульса по входу "установка нуля". Для записи
в регистр подается импульс записи, открывающий входные элементы И. код входного
числа записывается в регистр. По окончании операции записи информация,
записанная в регистр, сохраняется, несмотря на то, что входная информация может
изменяться. Для считывания информации подается импульс по входу
"Считывание". На выходные шины регистра передается код числа, записанный
в регистр. Параллельный регистр также выполнен на D-триггерах. На Рис. 13.
приведена схема параллельного регистра.
При считывании с параллельного регистра битов CRC-4 они попадают
на входы мультиплексора, который коммутирует их в поток Е1. на единственный
выход Y информация передается то с одного, то с другого входа поочередно, т.е.
мультиплексор подключает к входу по одной входной линии. Каждая входная линия (DI) имеет свой адрес (код). Выбор той или
иной линии осуществляется подачей соответствующего кода адреса на адресные шины
S1,. S4. на Рис. 14. приведена схема мультиплексора "из 16 в1".
Соответствие кодов адресов S0,S1,S2,S3 и входных линий
определяется таблицей истинности мультиплексора (Таблица 1).
По выходу из мультиплексора биты CRC-4 в строго определенное время
попадают на вход логического элемента И. ИЛИ, который в строго определенное
время вставляет их в поток Е1.
В результате разработки формирователя CRC-4 получилась схема,
приведенная на Рис. 15.
Заключение
В данном проекте был разработан блок формирователь CRC-4. В виду того, что
диаграммы представляют ожидаемые результаты, следует, что каждая схема в
частности, а значит и блок в целом, работают верно.
Данный блок имеет простую структуру, доступную для
последующего изучения и модернизации.
Литература
1.
И. И. Бобров - Импульсные и цифровые устройства 2008.
.
Е.Л. Кон, С.Н. Лицын, О.И. Шеховцов - Избыточное кодирование в системах
телемеханики и передачи данных 2011.
.
И.Г. Бакланов - Технологии измерений первичной сети. Часть1. Системы E1, PDH,
SDH 2008.
.
Ю.С. Забродин - Промышленная экономика 2010.
Похожие работы на - Формирователь СRC-4
|