Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 156
Скачиваний: 0
Если первоначально фильтр содержит нули, то при подаче на его вход полинома
S(x) = 5 o + SiX + S2X2 + . . . + SkXk
(предполагается, что коэффициенты полинома S(x) по ступают на вход, начиная с коэффициентов низших по рядков, после чего следует г нулей) на выходе получим произведение поли иомов
|
|
5 |
(х) |
G (х) |
= s0go + |
(sigo |
+ |
s0gi) |
х + |
|
|||
|
|
+ |
(s0g2 |
+ Sigi |
+ |
S2go)x2 |
+ |
. . . + |
|
Sl,grXh+r. |
|
||
Действительно, при подаче на вход коэффициента So |
|||||||||||||
на выходе получаем s 0 g 0 . |
В следующий |
момент |
времени |
||||||||||
Вход |
|
D |
D |
|
|
D |
|
|
D |
9г |
т2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ч0Г-/ |
|
|
|
Выход |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9г |
|
|
|
|
|
|
|
|
|
|
|
91 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а) |
|
|
|
|
|
|
|
Н Яг |
|
т2\ |
|
|
|
|
|
|
т2\ |
т2 Выход |
|||
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
Н |
|
Н В„ Н |
|
|
Вход |
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. |
3-1. Схема умножения |
на |
полином |
|
G(x) =ga+g\x+ |
... + |
|||||||
а — с |
одним миоговходовым |
сумматором |
по модулю |
два; б — с двувходо - |
|||||||||
|
|
|
выми сумматорами по модулю два. |
|
|||||||||
на вход поступает Si и |
на |
выходе |
|
фильтра получаем |
|||||||||
(stgo+Sogi) |
и т. д. Показанные схемы умножения |
много |
|||||||||||
членов |
могут |
использоваться |
в качестве |
кодера |
для не |
||||||||
разделимого циклического кода, заданного с помощью порождающего полинома G(x). Например, схемы коде ров для G(x) = 1 +х2+х3 показаны на рис. 3-2.
71
Вход Гд |
т2 |
Для осуществления |
ко |
|||||
дирования |
разделимым |
ци |
||||||
|
Выход |
|||||||
|
клическим |
кодом и вычисле |
||||||
|
|
ния корректора |
необходимо |
|||||
|
|
уметь строить |
схемы деления |
|||||
|
ЩВшоВ |
полиномов. Деление |
полино |
|||||
|
мов производится с помощью |
|||||||
|
|
|||||||
|
|
линейных |
|
ммоготактных |
||||
|
|
фильтров |
с обратными |
свя |
||||
|
|
зями. |
|
|
|
|
|
|
Рис. 3-2. Схемы кодеров для |
Рассмотрим |
произволь |
||||||
неразделимого |
циклического |
ный фильтр, |
содержащий г |
|||||
кода, порождаемого полиномом |
элементов задержки. Состоя |
|||||||
G(x) = |
l+x2+xh |
ние фильтра |
будем |
описы |
||||
а — с трехвходовым сумматором по |
вать вектором й = («1, юг,..., |
|||||||
модулю два; б — с двумя двувходо - |
со;-), где сог показывает |
зна |
||||||
выми сумматорами |
по м о д у л ю два. |
|||||||
|
|
чение двоичного символа, за |
||||||
|
|
поминаемого в i-м элементе |
||||||
задержки D. Нумерация элементов D производится |
сле |
|||||||
ва направо. В дискретные моменты времени, период сле
дования которых |
.равен |
величине |
задержки сигнала |
в элементах D, |
состояние |
фильтра |
изменяется. Если |
в качестве элементов задержки «спользуются триггеры, то период изменения состояний фильтра равен периоду
следования синхронизирующих |
сигналов, с помощью ко |
||||
торых производится сдвиг |
информации |
в регистре. |
|||
В |
автономном режиме 'новое |
состояние |
фильтра |
Q* = |
|
= |
(и*1, ш*2,-. .,а>*т) можно вычислить |
с помощью |
следу |
||
ющих соотношений: |
|
|
|
|
|
|
со*1=тцсй1 + /П12Сй2+. • . + |
tri\far; |
|
||
|
щ*2=/П21С01+т22;<»2+.. .-htfferuv; |
|
|
||
cu*r=/nricui+.m,.2Q)2+.. . + m„(j)r,
где triij—Л, если выход /-го элемента задержки связан со входом i-ro элемента; в противном случае пгц — О (сло жение и умножение являются операциями двоичного поля).
Эту систему уравнений можно переписать в матрич ной форме
Q*t = MQt или Q* = QM( ,
72
где М — квадратная матрица коэффициентов Мц, назы ваемая матрицей связей; — транспонированная мат рица М.
Например, матрица
0 0 |
I |
I |
|
м = || |
1 |
0 0 |
0 |
0 |
1 0 |
0 |
|
1*0 |
1 о |
||
соответствует фильтру, показанному на рис. 3-3.
Если исходное 'состояние фильтра равно Q, то последующие со стояния в автономном режиме будут равны:
QMt, (£2M,)M, = fiM2(...
Однако число различных ненулевых состояний фильтра не может превысить 2Г—-1. Поэтому найдется такое целое число /, не равное нулю, что ЙМ'( = Й. Множество состояний, которое принимал фильтр до тех пор, пока он «е перешел в исходное состояние Я, называют
|_|/772 |
D |
D |
Q L/772 |
D |
|
1 |
1 |
3 |
|
Рис. 3-3. Схема фильтра с обратными связями.
циклом. В общем случае длина цикла I зависит не только от матрицы связей М, но и выбранного исходного состояния. В связи с этим го ворят о структуре циклов фильтра.
Теорию многотактных фильтров с обратными связями применительно к вычислению остатка от деления двух полиномов можно изложить следующим образом. Век тор-столбцам матрицы М поставим в соответствие поли номы степени г—1 таким образом, что
г
/ = |
Тогда матрицу М можно записать в виде
M = | | f t ( j c ) , М-*) М-*)||. |
(3-6) |
73
|
Если |
|
|
|
|
|
j i g |
(JC) =н лц, (л) ss 1; |
|
|
|
|
по модулю G(x), |
Ji, (Л") sa ЛV, (Л') = Х\ |
|
|
|
|
||
|
|
|
|
|
||
(ir |
(Л") s=,Xr V,(A')s=A-r 2 , |
|
|
|
(3-7) |
|
|
|
|
|
|
|
|
то соответствующая |
матрица |
|
связей |
|
||
|
|
Si |
1 |
0 . |
. 0 |
|
|
М |
gi |
0 |
1 . |
. 0 |
(3-8) |
|
= |
|
|
|
||
|
|
gr- |
0 |
0 . |
. I |
|
|
|
gr |
0 |
0 . |
. 0 |
|
Тогда состояние фильтра в следующем такте
Q*(x) З = Й М ( = = С О 1 Д ; - 1 + |
С О 2 + : С О З А : + |
.. . +©г х''-2 == |
|
= (ац + <йгХ + ... |
+(arxr~i)x-l |
= Q(x)x-i |
помодулю G(x). |
|
|
|
(3-9) |
Входную цепь |
фильтра |
построим |
таким образом, |
чтобы Q*(x) =[Q(x) |
+s]x-x |
по модулю |
G(x), т. е. после |
дующее состояние получается прибавлением входного
символа s к содержимому фильтра |
и однократным сдви |
|||||||||
гом влево в автономном режиме. |
|
|
|
|
|
|||||
|
Если начальное состояние Q(°)(je)=0 и на вход филь |
|||||||||
тра |
поступает последовательность |
символов |
So, Si, s2, .. . |
|||||||
..., |
s |
n - i [эта последовательность соответствует коэффици |
||||||||
ентам |
полинома |
S(x)=So |
+ siX+S2X2+.. |
|
.-\-sn-iXn~l], |
то |
||||
фильтр будет последовательно принимать состояния |
||||||||||
Q<2> (х) s= (vc~ 1 + |
s.) х-1 |
== sQx~2 |
+ |
s, х ~ |
по |
модулю |
||||
Q<n> (JC) == s0x ~n ' + |
SlA - <r t _ 1 > -f-... + |
s„ _ ,x - 1 . |
G(x). |
|||||||
|
|
|||||||||
|
* Сравнение X-1 |
= \JH{X) |
по модулю |
G{x) |
эквивалентно x\ii{x) = |
|||||
= 1, тогда xy.i(x) = G{x) |
+ |
1 = {go + 1) + |
gtx+ . . . |
+ £ , л : г = * ( £ | - г - |
||||||
+ g 2 |
* + |
. . . +grXr~l), |
а |
отсюда следует |
Ц| (д;) =g1+g2x+ |
. . . |
||||
. . . |
|
+grXr~l. |
|
|
|
|
|
|
|
|
74
Или, |
учитывая |
сравнение хп = \ |
тго модулю |
G(x), |
|
получаем: |
|
|
|
|
|
QW(x)s=s0 |
+ SiX + .. . + sn-ix(-n-i'>^S(x) |
по модулю |
G(x). |
||
Следовательно, после поступления последнего сим |
|||||
вола s n - i |
содержимое |
фильтра будет |
равно остатку от |
||
деления полинома S(x) |
на G(x). |
|
|
||
Структура фильтра, |
описываемого матрицей |
связей |
|||
(3-8), показана на |
рис. 3-4. Данная |
схема может |
быть |
||
Рис. |
3-4. Схема одиоканального |
кодера для циклического раздели |
|
мого |
кода, порождаемого полиномом G(x) = l+g^x+ . . . +gT-\XT-[ |
+ |
|
|
+ |
grXr. |
|
использована для вычисления контрольных разрядов раз делимого циклического кода в соответствии с выраже нием (3-3). Кодер работает следующим образом. Снача ла ключ К находится в нижнем положении и k = n—г информационных разрядов (v0, vu ..., u^-i) поступают на вход фильтра, который вначале находится в нулевом состоянии, и непосредственно в линию связи. Затем ключ К переключается в верхнее положение. В этом случае обратная связь в фильтре размыкается и г контрольных разрядов последовательно «выдвигаются» в линию. Та ким образом, к концу передачи кодового слова фильтр оказывается в нулевом состоянии.
Формально работа кодера описывается следующим образом. После поступления k информационных симво лов содержимое фильтра равно:
|
QM(x) |
^VoX-'l |
+ vix-(h-i)+.. |
. + |
vh-lx-i^ |
|
=x-h(v0 |
+ ViX+.. . + vil-ixk-i)=x-hV(x) |
по модулю G(x), |
||||
что совпадает с выражением (3-3). |
|
|
|
|||
Корректирующее устройство служит для проверки |
||||||
выполнения условия (3-1), т. е. если |
принятый |
полином |
||||
соответствует |
кодовому |
слову, то он должен |
делиться |
|||
на G(x). |
Если |
же возникла ошибка |
Е(х)=х{е(х), |
кото- |
||
75
рая принадлежит к множеству ошибок, корректируемых данным кодом, то по полученному остатку от деления
Е(х) |
на |
G(x) |
(корректору) |
ошибка может быть |
исправлена. |
|
|
||
Структурная схема КУ показана на рис. 3-5. Коэффи |
||||
циенты а0, |
ait- • -An-i полинома |
А(х) последовательно по |
||
ступают на вход буферного ЗУ, в качестве которого
обычно используется n-разрядный сдвигающий |
регистр, |
и одновременно на вход блока деления А(х) на |
полином |
ill
|
Блок |
|
лс |
|
деления на S(x) |
± |
|
|
|
||
|
|
|
|
Вход |
Буферное ЗУ |
Ц/772 Выход |
|
|
|||
|
|
||
Рис. 3-5. Структурная схема КУ для циклического кода.
G(x) (многотактный фильтр). Если А(х) является кодо вым словом, то через п тактов содержимое блока деле ния (корректор) станет равно нулю. При появлении об наруживаемой ошибки корректор с<-°)(х)Ф0. Если про должить работу (синхронно производить сдвиги содер жимого буферного ЗУ и блока деления в автономном режиме), то последовательные состояния блока деления или значения корректора будут равны:
|
|
по модулю |
G(x), |
е<*> (х) == х°е (х) = |
е (х), |
|
|
т. е. вычет е(х) |
будет |
воспроизведен |
точно через |
i тактов. |
|
|
|
Впростейшем случае, когда возникла одиночная
ошибка Е(х)=х\ т. е. е(х) — \, на им такте сЮ(х)=<1
или содержимое запоминающих ячеек блока деления будет равно 10.. .00. При появлении этой комбинации на выходе логической схемы должен появиться сигнал, ко торый поступит на вход сумматора по модулю 2 и инвер тирует ошибочный символ. Таким образом, при исправ лении одиночных ошибок в одноканальном КУ логиче ская схема (ЛС) (рис. 3-5) представляет собой схему
76