Файл: Теория и техника передачи данных и телеграфия учебник..pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.04.2024
Просмотров: 285
Скачиваний: 1
элементов г)о больше т]и примерно в 100 и 1000 раз соответ ственно.
§ 6.7. |
Кодирующие и декодирующие |
устройства |
||
|
циклических |
кодов |
|
|
6.7.1. |
Процедура |
кодирования |
и |
декодирования |
|
для |
циклических |
кодов |
|
В основе процедуры кодирования циклических кодов лежит |
||||
методика формирования |
кодовой |
комбинации, в соответствии |
||
с которой кодирующее устройство должно выполнять умно
жение |
ai(x) |
комбинации |
первичного |
кода, |
представляемой |
|||||||||
многочленом |
степени, |
не |
старшей k — 1, на |
xn~k, |
|
деление по |
||||||||
лученного |
в |
результате |
умножения |
многочлена xn~kal(x) |
сте |
|||||||||
пени, |
не |
превышающей |
я — 1 , |
на |
порождающий |
многочлен |
||||||||
кода g |
(х) |
степени п — k, |
и |
вычисление |
остатка |
от этого |
д е |
|||||||
ления |
Г; (х) |
|
степени п — k — 1 |
или |
менее. |
В |
сформированной |
|||||||
комбинации |
циклического |
кода |
коэффициенты |
|
многочлена |
|||||||||
x"-kai(x) |
|
являются информационными элементами, а коэф |
||||||||||||
фициенты |
многочлена |
rt(x) |
— избыточными. |
|
|
|
|
|
||||||
В основе процедуры декодирования лежит процесс выяв |
||||||||||||||
ления |
принадлежности |
принятой |
комбинации |
к |
множеству |
|||||||||
разрешенных |
кодовых |
комбинаций. |
Эта задача решается вы |
|||||||||||
числением |
синдрома |
для |
каждой |
принятой |
|
комбинации |
St =• |
|||||||
—Vfl{n, k).
Технически реализация данной операции может осущест вляться по той же методике, что и для кодов Хэмминга (п. 6.5.1). Однако, можно построить более рациональную процедуру вычис ления синдрома для циклических кодов, если использовать при
знак |
делимости кодовой комбинации на порождающий |
много |
|||
член |
g(x). |
В этом случае принятую кодовую |
комбинацию |
fi{x) |
|
Делят на порождающий многочлен кода g(x). |
Если остаток |
от |
|||
деления |
г,-(л) = 0 , то считают, что данная комбинация |
fi(x) |
и |
||
была передана, и k элементов, т. е. коэффициентов при старших
степенях |
fi(x), |
поступают |
потребителю |
в |
качестве |
переданного |
|||||||||||
сообщения. Если же остаток от деления |
Г І ( Х ) |
=^0, |
то |
принятую |
|||||||||||||
комбинацию }г(х) |
бракуют и потребителю |
выдают |
сигнал |
«Сти |
|||||||||||||
рание» |
или производят исправление |
ошибок. |
|
ri |
(х) |
|
|
|
|||||||||
При |
исправлении |
ошибок |
по |
виду |
остатка |
опреде |
|||||||||||
л я ю т наиболее вероятный образец |
ошибки, |
инвертируют |
эле |
||||||||||||||
менты, |
в которых предполагаются ошибки, и |
выдают |
потре |
||||||||||||||
бителю |
информационные |
разряды |
комбинации. |
Покажем, |
что |
||||||||||||
остаток |
rt(x) |
тождествен |
синдрому в общепринятом |
опреде |
|||||||||||||
лении, |
т. |
е. |
Г[(х) |
= |
St = |
VtH[„,k). |
Как было, установлено . вы |
||||||||||
ше, столбцы проверочной |
матрицы |
есть остатки от деления |
х0, |
||||||||||||||
х , . . . , х"-1 |
на |
порождающий |
многочлен |
g(x). |
Известно, |
.что |
|||||||||||
'Деление |
|
обладает |
свойством |
суперпозиции, |
т. |
е. |
остаток |
от |
|||||||||
деления |
|
многочлена ft(x) |
на |
многочлен g(x) |
равен |
сумме |
||||||||
остатков |
от деления степеней xi с |
ненулевыми |
коэффициен |
|||||||||||
тами из |
этого многочлена на g(x). |
Так |
как |
вычисление |
про |
|||||||||
изведения |
Vfiln, k ) |
СВОДИТСЯ |
К |
Суммированию |
СТОЛбцОВ H(n,ft), |
|||||||||
которым |
соответствуют |
ненулевые |
элементы |
принятой |
комби |
|||||||||
нации, то |
произведение |
V^\[ntk) |
в точности |
равно остатку от |
||||||||||
деления |
многочлена /, (х), |
соответствующего |
комбинации |
Vh |
||||||||||
на порождающий многочлен g(x). |
Итак, |
для |
вычисления |
син |
||||||||||
дрома Si—Гііх) |
необходимо |
иметь |
схему деления на порож |
|||||||||||
дающий |
многочлен |
g(x). |
|
В |
случае исправления |
ошибок |
по |
|||||||
требуется еще и схема сопоставления синдрома |
образцу |
|||||||||||||
ошибки. |
|
|
6.7.2. |
Схема |
|
кодирующего |
|
устройства |
|
|
|
|||
|
|
|
|
|
|
|
|
|||||||
В основе кодирующего устройства лежит схема деления на порождающий многочлен g(x) степени n—k с предварительным умножением на xn~h. Общий вид схемы кодирующего устройства
|
|
|
|
|
|
1 |
|
|
|
Рис. «.8. |
|
|
|
изображен на рис. 6.8. Число ячеек памяти в регистре |
(/ч) равно |
|||||
n—k, |
т. е. числу |
избыточных элементов |
кодовой комбинации. |
|||
Обратные связи |
(gi) |
подключены в соответствии с ненулевыми |
||||
коэффициентами |
g(x),. |
следовательно, общее |
число |
обратных |
||
связей |
равно числу компонент g(x) (или |
весу |
в двоичном пред |
|||
ставлении). Число сумматоров по модулю 2 равно числу знаков
« + » в записи |
g(x). |
Вход схемы |
подключен после ячейки Гп-ft-i для осуществле |
ния, .предварительного умножения кодируемой комбинации йі(х) |
|
на хп~К Схема работает следующим образом. Информационные элементы а, (х) поступают на вход кодирующего устройства, на чиная со старшей степени, и одновременно на выход схемы — в канал связи. В это время на схему И\ в цепи обратной связи подаются k тактовых импульсов от управляющего устройства и со входа информационные импульсы поступают через цепь об ратной связи в разряды регистра. Когда все k 'информационных
16* |
^43 |
элементов будут ©ведены в устройство, в (разрядах регистра будут сформированы проверочные элементы ГІ(Х) К О Д О В О Й комбинация. По прошествии k тактов подача тактовых импульсов в схему И\ прекращается, т. е. линия обратной связи разрывается и п — к проверочных элементов, сформированных в регистре, через схему
# 2 , на которую |
начинают поступать тактовые импульсы от |
|
(&+1) - го до п-то |
такта, выводятся в канал связи сразу |
ж е за |
информационными |
элементами. Таким образом, за п |
тактов |
с выхода схемы в канал поступает вся кодовая комбинация цик лического (я, k) -кода.
П р и м е р . Построить кодирующее устройство для циклического (7,4)-кода с порождающим многочленом g(x) = 1 + х + х3 и проследить по тактам про цесс формирования кодовой комбинации.
|
|
|
|
|
Рис. |
6.9. |
|
|
|
|
|
|
|
В соответствии с рис. 6.8 |
и видом |
g(x) |
составляем схему |
кодирующего |
|||||||||
устройства, |
которая |
содержит |
разряды |
г0, |
п, |
ъ |
и обратные |
связи go, gi, |
ёз |
||||
(рис. |
6.9). |
|
|
|
|
|
|
|
|
|
|
|
|
Процесс |
кодирования |
комбинации |
простого |
кода 0 1 0 |
1 |
представлен в |
|||||||
таблице. |
|
|
|
|
|
|
|
|
|
|
|
|
|
№ |
Вход |
Состояние |
разрядов |
Вход |
Выход |
Примечание |
|
||||||
такта |
|
Го |
|
|
|
# i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
|
0 |
0 |
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
|
0 |
1 |
|
|
1 |
|
|
|
|
2 |
0 |
0 |
1 |
|
1 |
0 |
|
0 |
Тактовые |
импульсы |
по |
||
|
|
|
|
|
|
|
|
|
|
||||
3 |
1 |
0 |
0 |
|
1 |
0 |
|
|
1 |
ступают |
на Pfi |
|
|
4 |
0 |
1 |
1 |
|
0 |
I |
|
|
0 |
|
|
|
|
5 |
0 |
0 |
1 |
|
1 |
0 |
|
|
0 |
Тактовые |
импульсы |
по |
|
6 |
0 |
0 |
0 |
|
1 |
1 |
|
|
1 |
||||
7 |
0 |
0 |
0 |
|
0 |
1 |
|
|
1 |
ступают |
на Из |
|
|
|
|
|
|
|
|
|
|||||||
Для оценки правильности процесса кодирования определим алгебраи
чески |
комбинацию |
циклического |
(7,4)-кода, |
соответствующую |
рассмотрен |
|||||||||||
ной комбинации at |
(х) = 0101 |
= х |
+ |
х3. Находим в,- (л:) хп~к |
= |
(х + |
х*) х3 = |
|||||||||
= х* + |
Разделив а,- (х) хп |
|
на |
£ |
(х), |
получим |
проверочные |
элементы |
||||||||
кодовой комбинации |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
1 + х |
+ |
хз |
|
|
|
||
|
|
|
Хг |
+ Xі |
+ JC6 |
|
Xі |
| 1 |
|
|
|
|
|
|
||
|
|
Є |
х 3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 + х + |
х* |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 + X |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
результате |
решения |
имеем |
|
q, |
(х) |
= |
1 -f- jr3 |
|
и |
г/ (х) = 1 -)- ж. Следо |
|||||
вательно, соответствующая |
кодовая |
комбинация |
есть |
п(х) |
+ |
at(x) |
хп~к— |
|||||||||
= 1 -\- х + х* + х* =r- 1 1 0 0 1 0 1. |
|
|
|
|
|
|
|
|
|
|
||||||
|
6.7.3. Схелш декодирующего |
|
|
устройства |
|
|
||||||||||
|
|
при |
обнаружении |
|
|
ошибок |
|
|
|
|
||||||
Декодирующее устройство, использующее свойство делимости кодовой комбинации на порождающий многочлен, приведено на рис. 6.10. Элементы кодовой комбинации после регистрирующего устройства последовательно вводятся в схему деления на g{x).
Вход |
3-й |
<аколате/>б i/i |
Выход |
||
|
ционных разря |
|
|
||
|
Схема де/ген&я |
|
|
|
|
|
над.(х) |
|
|
|
|
|
• |
: : |
г* |
± |
|
|
—\ |
і — " — 1 |
|
|
|
|
|
Рис. |
6.10. |
|
|
Информационные элементы комбинации записываются также в накопитель информационных разрядов. После ввода последнего элемента принятой комбинации в схему деления разряды ре гистра сдвига этой схемы содержат остаток от деления принятой комбинации на g(x). Если остаток чисто нулевой, то комбинация считается принятой верно; если же остаток не равен нулю, то фиксируется прием с ошибками.
С целью принятия решения о наличии или отсутствии ошибок |
|
в .примятой комбинации разряды регистра схемы деления под |
|
ключаются |
к схеме ИЛИ. Если ошибки отсутствуют (или не об |
наружены), |
то после ввода всей комбинации в декодирующее |
устройство на выходе схемы ИЛИ вырабатывается сигнал «0», по которому информация из накопителя информационных разря дов выдается потребителю информации. В том случае, когда на выходе схемы ИЛИ появится «1» (это произойдет, когда хотя
бы в одном из разрядов регистра |
после деления |
останется «1», |
т. е. полученный остаток не равен |
нулю), информационные раз-, |
|
ряды из накопителя не выдаются |
потребителю |
и фиксируется |
ошибка. |
|
|
П р и м е р . Построить декодирующее |
устройство для обнаружения оши |
|
бок циклическим (7,4)-кодом с g(x) = 1 + х + XІ и проследить процесс выяв
ления ошибок. Схема декодирующего устройства для данного случая изобра жена на рис. 6. И.
Вхоо1 |
|
выход |
|
<*1 |
Go |
||
|
Шко/ште/гь
информационны^
разрядоі
Схема
делений на о (ж)
Рис. 6.11.
Пусть приемное устройство зарегистрировало комбинацию 1 1 0 0 1 0 1. Состояние элементов схемы деления в процессе ввода в нее данной комбина ции отражено в таблице.
№ |
|
Состояние |
разрядов |
регистра |
Цепь |
Вход |
|
|
|
обратной |
|
такта |
|
|
|
||
|
Го |
|
|
связи |
|
|
|
|
|
||
|
|
|
|
|
|
0 |
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
3 |
1 |
1 |
0 |
1 |
0 |
4 |
0 |
1 |
0 |
0 |
1 |
5 |
0 |
0 |
1 |
0 |
0 |
6 |
1 |
1 |
0 |
1 |
0 |
7 |
1 |
0 |
0 |
0 |
1 |
Таким образом, в процессе деления установлено, что принятая комбинация принадлежит циклическому (7,4)-коду и ее информационные элементы вы даются потребителю информации. Предположим теперь, что ошибочно принят первый элемент комбинации и принятая комбинация имеет вид 1 1 0 0 1 0 0. Процесс вычисления оимдрома приведен в таблице.
Для принятой комбинации синдром имеет ненулевое значение 1 0 1 и на выходе схемы ИЛИ появится сипнал, запрещающий выдачу информационных
элементов потребителю.
