Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 163
Скачиваний: 0
гi
фильтр |
г • |
ЛС |
|
||
|
|
|
|
|
т2 |
|
|
Цт2 |
Буферное ЗУ |
Чт2 |
|
|
|
|
Рис. 3-7. Структурная схема v-канальяого КУ.
а последующие состояния при автономной работе равны:
|
|
|
|
I |
— (Z'V—Я)—V • |
|
|
|
|
|
|
|
|
|
: Л. |
|
[, |
по модулю G(x). |
|||||
|
|
|
|
I |
— (z'v—/()—2v |
||||||
Пусть i=jv+$ |
|
№ < ^ Л т. е. |
ошибка |
должна быть |
|||||||
исправлена |
в такте у + 1. Тогда |
на /-м такте |
автоном.о"! |
||||||||
работы состояние фильтра равно: |
|
|
|
|
|||||||
|
|
=цх9~{гЧ~п) |
по модулю |
G(x), |
|
|
|||||
т. е. ЛС должна |
распознавать |
следующие |
вычеты по |
||||||||
•модулю |
G(x) |
|
|
|
|
|
|
|
|
|
|
при |
р = |
0 |
х~ • (z'v—п) |
, |
|
|
|
|
|
||
при р = 1 |
х 1 — (z'v — л) |
|
|
|
|
|
|||||
при |
р = |
v — 1 |
X 1—1 — (z'v—л) |
|
|
|
|
|
|||
Например, |
пусть |
п=7, |
v = 2 , G(A') = 1+хг+х3, |
тогда |
г ' = 4 и Л С |
||||||
представляет |
собой |
две схемы совпадения |
на следующие |
коды: |
|||||||
при 6=0 x - 1 |
s x ' - i = J T B = ^ + X 2 | т _ е |
o i l , |
|
|
|
||||||
при р = 1 х1~1=х? |
= \, т. е. 100. |
|
|
|
|
|
|||||
В заключение рассмотрим способ вычисления матриц М* и F*, входящих в матричное уравнение (3-10), исклю чающий необходимость возведения в степень и перемно жения матриц. Пусть исходное состояние фильтра (одноканального) равно Q<°)(x). Тогда в соответствии с выра жением (3-9) состояние фильтра после v-ro такта работы в автономном режиме будет равно:
Q ( V ) ( X ) = Q ( ° ) ( A ; ) ^ _ v по модулю G(x).
6—236 |
81 |
С другой |
стороны, |
это |
состояние |
определяется |
Мат |
|
ричным выражением |
|
|
|
|
|
|
|
Q( v ) |
= Q C » ) M v . |
|
|
|
|
|
|
|
t |
|
|
|
Приравнивая правые части этих выражений,получаем: |
||||||
a<°)(.\:)x_ v = |
Q(0 'Mv t по модулю G(x) |
|
||||
или |
|
|
|
|
|
|
|
Q(°) |
„\TV =Q<°>MV |
|
|
||
отсюда следует, что |
|
X |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
„—v + l |
|
|
|
|
|
х |
= |
по модулю G(x). |
|
||
|
|
„ r - v - l |
|
|
|
|
Другими |
словами, |
вектор-столбцы |
матрицы связен |
|||
v-канального фильтра равны: |
|
|
|
|||
М* = \\х~\ |
х-*+1,..., |
x r |
_ v _ ' | | по модулю |
G(x). |
(3-11) |
|
'Вектор-строки матрицы |
F* вычисляются |
следующим |
||||
образом: |
|
|
|
|
|
|
...-\-grxr~i)=s=x~ix~1 |
= x~ ( г + 1 ) |
по модулю |
G(x). |
|
Таким образом, вектор-строки |
матрицы |
F* |
равны: |
|
- ( V - I ) |
|
|
|
|
|
по модулю G(x). |
|
(3-12) |
|
х-1 |
|
|
|
|
82
Например, пусть требуется построить пятиканальную схему де
ления для реализации циклического |
кода, |
порождаемого |
полиномом |
|||||||||
G(x) = 1+х+х2+х'1+х8. |
Матрица |
связен |
|
в |
соответствии |
с выраже |
||||||
нием (3-11) равна: |
|
|
|
|
|
|
|
|
|
|
|
|
М 5 |
|
|
|
|
|
х, |
х 2 1 | |
по |
модулю |
G (х);- |
||
отсюда |
0 |
0 |
1 0 |
1 |
1 0 |
0 |
|
|
|
|
||
|
|
|
|
|
||||||||
|
0 |
0 |
1 1 1 0 |
|
1 0 |
|
|
|
|
|||
|
1 0 |
1 |
1 0 |
0 |
0 |
1 |
|
|
|
|
||
|
1 1 0 |
|
1 1 0 |
|
0 |
0 |
|
|
|
|
||
М5 |
1 0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
||
|
1 |
|
|
|
|
|||||||
|
0 |
1 |
1 0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
1 0 |
1 |
1 0 |
0 |
0 |
0 |
|
|
|
|
||
|
0 |
1 0 |
1 |
1 0 |
0 |
0 |
|
|
|
|
||
Аналогично на |
основании |
выражения |
(3-12) |
получаем: |
||||||||
|
х - 6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
по |
модулю |
G (х); |
|
||||
отсюда |
|
0 |
0 |
1 1 1 0 |
1 0 |
|
|
|
||||
|
|
|
|
|
||||||||
|
|
0 |
0 |
0 |
1 |
1 |
1 0 |
1 |
|
|
|
|
|
F * = || 1 1 1 0 0 1 1 0 |
|
|
|
||||||||
|
|
0 |
1 1 1 0 |
|
0 |
1 1 |
|
|
|
|||
|
|
1 |
1 |
0 |
1 0 |
0 |
0 |
1 |
|
|
|
|
Искомая схема |
деления |
показана |
|
на рис. |
3-8. |
|
|
|||||
3-4. МАЖОРИТАРНОЕ Д Е К О Д И Р О В А Н И Е ЦИКЛИЧЕСКИХ КОДОВ
Пусть Н — проверочная матрица циклического (п, k)- кода. Все возможные линейные комбинации строк матри цы Н задают совокупность проверочных соотношений (уравнений) для рассматриваемого кода. Выберем т проверочных соотношений, содержащих на первой слева позиции единицу:
(/г»,о, hi,i,-. .,hi,n-0. t = |
1, 2.- -пт> |
б* |
§3- |
ад
4 2 ] в : : Ж ]
::f>2\_
Рис. 3-8. Пятиканальная схема деления на поли
ном G(x) = |
\+x+x*+x*+xa. |
где fti,o=l. Пусть S = (sQ, |
SI, Sz,.. .,sn-i) является кодо |
вым словом, тогда должны выполняться следующие т
•контрольных соотношений: |
|
( |
|
|
s<A\o + s A \ i + -- + s T i - A \ n - i = |
£ |
SjAfj=0 |
по модулю2, |
|
i = 1, |
2 |
т. |
|
|
Так как /40 =1, то эти уравнения можно |
решить от |
|||
носительно символа so.- |
|
|
|
|
л—1 |
|
|
|
|
s£° = 2 Sjhij, |
i = l , 2 |
т. |
|
|
К данной системе уравнений .можно добавить триви альное уравнение s(%=s0 .
84
Таким образом, получено (т+1) уравнений для де кодирования символа So. Из определения циклического «ода следует, что рассмотренные соотношения также де кодируют все остальные символы. Так что в общем случае
п<°> |
• s |
, а = 0, |
1 |
п — 1; |
|
л—I |
|
|
(3-13) |
|
|
|
|
|
i ° = |
S |
s.hi^, |
i = |
l , 2,..., т. |
где суммирование индексов при s производится по модулю п.
Пусть каждый столбец, исключая первый слева, мат рицы Н0 , в качестве вектор-строк которой выбраны упо мянутые т. векторов, содержит не более X единиц. Тогда алгоритм 'мажоритарного декодирования, основанный на
решении ( т + 1 ) уравнений системы (3-13), |
позволяет |
исправлять любые t или менее ошибок, где |
t=[m/2X]. |
Квадратными скобками обозначена операция округления до ближайшего меньшего целого числа. Число X назы вают показателем связности системы контрольных соот ношений. Если Х=1, то говорят о системе разделенных контрольных соотношений.
В качестве примера рассмотрим систему А,-связанных контроль ных соотношений для циклического кода Хэмминга (7,4), порождае мого полиномом G(x) = l+xz+x3. Контрольная матрица этого кода равна:
л, |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
н = Л 2 |
0 1 1 1 0 |
1 |
0 |
||||
Аз |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
Из этой матрицы можно получить матрицу Но, вектор-строки ко торой задают контрольные соотношения с показателем связности
Х=2:
|
1 |
1 1 0 |
1 0 |
0 |
|||
|
1 |
0 |
0 |
1 1 1 0 |
|
||
А, |
1 |
1 |
0 |
1 0 |
0 |
1 |
|
Л , + Л 2 |
1 |
0 |
1 0 0 1 1 |
||||
85
Таким образом, в данном случае пблучаем пять уравнении, опре деляющих значение декодируемого символа s<j:
О— io>
4 2 ) = s 3 + ^ + s5 ; j . no модулю 2.
4 3 > = ^ + s 3 + S ( ! ;
При этом любая одиночная ошибка нарушит не более двух урав нений и безошибочное значение символа So определяется с помощью мажоритарного элемента иа пять входов. Декодирование остальных символов производится аналогично:
с(2)
|
s | 4 1 = s 2 + i |
+ s 5 + i + |
s a + i , |
|
|
|
где суммирование индексов |
производится |
по модулю |
п=7. |
|
||
Схема КУ, реализующая полученные соотношения, показана на |
||||||
рис. 3-9. Вначале ключ К находится п |
положении |
Прием |
и слово |
|||
S=(s 0 , si, ... , |
«б) принимается |
схемой. Затем ключ К переключается |
||||
в положение |
Декодирование |
и |
производится последовательное деко |
|||
дирование полученных символов с помощью мажоритарного |
элемен |
|||||
та & М. Декодируемые символы |
поступают па вход схемы, т. е. про |
|||||
исходит циклический сдвиг принятого слова. |
|
|
||||
Выход
Рис. 3-9. Схема КУ для циклического |
(7,4)-кода, порождаемого |
полиномом G (х) = 1 + |
х 2 + х 3 . |