Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 174
Скачиваний: 0
|
|
|
i |
i |
i |
•6 |
0 |
|
1 |
|
|
|
|
|
l |
1 |
1 |
0 |
|
0 |
1 |
|
н * |
= |
|
|
1 |
1 |
1 |
|
0 |
0 |
|
|
|
|
1 |
1 |
|
1 |
0 |
||
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
1 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
«1-5 |
|
s i - 3 |
|
Si- |
Si |
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
0 |
|
|
1 |
|
|
0 |
0 |
0 |
1 |
0 |
0 |
|
• |
О |
1 |
|
0 |
0 |
0 |
0 |
1 |
0 |
|
|
о |
о |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
si + a |
si+i |
|
|
Ci + |
l |
|
i+4 |
|
c t + 6 |
|
Из первой, четвертой и шестой строк данной матрицы следуют уравнения, правые части которых не содержат общих членов:
s.=Si_5+Si-4+Si-3+Ci; S: = £.-2 + S • -1 + SI +3 + С(+3; Si = -Si+l + Sj+2 + Si+5+Ci+5.
Добавляя к этим уравнениям тривиальное |
5, = s,-, |
получаем си |
|||||||
стему |
из |
четырех независимых |
уравнений. |
На |
|
рис. |
4-5 |
показана |
|
схема |
КУ |
(ср. с |
рис. 4-4). Задержка при декодировании |
составляет |
|||||
пять |
тактов, отсчитываемых с |
момента прихода |
первых |
символов |
|||||
(s0, Со). |
|
|
|
|
|
|
|
|
|
Вход |
|
|
|
|
D |
D |
|
|
|
информацион |
|
|
|
S/-t Т |
S)-s |
|
|
||
ных символов |
|
|
|
|
|
/772 |
|
||
|
|
|
|
|
|
|
т2 |
выход |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7772 |
|
|
|
|
Вход |
C/.J |
В |
о |
|
|
|
|
|
|
контрольных символов |
СМ |
|
|
|
|
|
|
Рис. 4-5. Схема |
КУ для бессиидромного декодирования |
кода, порож |
|||||||
|
|
даемого полиномом G(x) = |
1+х3+х*+х5. |
|
|
||||
102
При бессиндромиом декодировании без размножения ошибок декодер содержит г дополнительных запоминающих ячеек, и увели чивается длина последовательности, на которой реализуется рас стояние б:
m'=3(; + l ) — 1 = З г + 2 |
(4-9) |
символов вместо 2(г+1) символов.
Обобщим теперь понятие сверточиого кода на случай произ вольной скорости передачи kin двоичных единиц на передаваемый символ. Будем предполагать, что код разделимый, т. е. в каждый дискретный момент времени на вход кодера поступают k инфор мационных символов, а с выходов считываются и символов, первые из которых повторяют информационные, а остальные п—k являются линейными комбинациями входных последовательностей. Если вход
ные |
(информационные) |
последовательности |
обозначить через |
||||||||||
|
|
|
SO) (х) = |
4 " + s\l)x |
+ 4 ' ' х г |
+ |
|
|
|
||||
|
|
|
ДО (X) |
= S(V |
+S\k)X |
+ |
S^X* |
+ . . . , |
|
|
|
||
а |
выходные контрольные последовательности — через |
|
|
|
|||||||||
|
|
|
СО)(х) |
= с ( " + с<1 ) х + |
4 1 ) х 2 + . . . ; |
|
|
|
|||||
|
|
С<»-*> (х) = |
|
+ c\n~k)x |
+ |
4''-f t >x= + . . . . |
|
|
|||||
то по условию |
|
|
|
|
|
|
|
|
|
|
|||
|
|
CU)(x) = GO)(x)SW(x)+mi)(x)SW(x)+ |
. . . +Z<J>(x) S<''>(*), |
(4-10) |
|||||||||
где |
&»(х), |
НМЦх) |
|
ZO){x), j=\, |
2 |
n—k |
называют по |
||||||
рождающими полиномами. Таким образом, в |
общем |
случае сверточ- |
|||||||||||
ный |
код порождается |
k{n—k) |
полиномами. |
|
|
|
|
||||||
|
|
Кодовое |
ограничение в этом |
случае |
|
|
|
|
|
||||
|
|
|
|
|
|
т=п(г+\), |
|
|
|
|
|
|
|
где |
г—наибольшая |
из степеней |
порождающих полиномов. |
|
|||||||||
|
|
Дерево, соответствующее коду, будет выглядеть |
несколько ина |
||||||||||
че, |
чем на рис. 4-2. Теперь из каждого |
узла |
исходят |
не две |
ветви, |
||||||||
а |
2й ; закодированная |
последовательность получается |
считыванием |
||||||||||
n-разрядных слов, стоящих снизу ветвей, находящихся на заданном пути.
Для выполнения операции кодирования в соответствии с выра
жением (4-10) применяются |
схемы, аналогичные |
показанным |
на |
рис. 3-1. |
|
|
|
Если принятые (возможно |
с ошибками) информационные последо |
||
вательности S</> (х), ... , 5<*)(х), где S</> (х) = ДО(х) |
+ £(*>(х), |
за |
|
кодировать |
и |
сложить с |
принятыми контрольными последовательно |
стями |
(х), |
... , C<," |
-f t ) (x), где С</> (х) = CU) (х) + ЕМ (х), то |
103
получим (п — k) корректирующих последовательностей: |
|
|
|||
№ |
(x)=GO) (x)S<" (x)+HO)(x)S}t2)(x)+...+Z(i)(x)S«ft)(x)+C</)(x) |
|
= |
||
= |
GO) (x) EC) (x) -f- HO) (x) £(=) (x) + |
. . . + Z<n(x)£№(x)4-£(h +>>(x), |
|||
|
|
|
|
|
(4-11) |
|
|
/ = 1 , 2 |
л — A. |
|
|
|
Символы корректирующих последовательностей используются для |
||||
определения k шумовых символов е^1 ', |
, ... , <?'0*\ т. |
е. |
проверки |
||
правильности приема |
первых /г информационных символов s^1' |
s[)fc' . |
|||
Затем декодируется |
вторая группа символов s{'' |
s j & ) |
и т. д. |
||
Значения символов корректирующих последовательностей, получае мых согласно выражению (4-11), вычисляются с помощью следую щего матричного уравнения:
где Hi—транспонированная контрольная матрица сверточного кода, которая имеет размер (n—k) (r+l) X /i(/"+.1);
Ограничимся рассмотрением таких классов сверточных кодов, которые позволяют использовать мажоритарный способ декодирова ния. В этом случае коэффициенты k(n—k) порождающих полиномов должны быть выбраны так, чтобы получить систему разделенных относительно шумовых символов е( 1 'о, е<2>о, . .., е(*>о контрольных соотношений. В табл. 4-5 даны некоторые сверточные коды, най
денные Месси и Рычннковым [Л. 30, 32]. Разделенные |
контрольные |
|
соотношения определяются из контрольной матрицы Н |
(см. стр. |
105). |
При бесснндромном декодировании реализуемое расстояние |
уве |
|
личивается на единицу (однако на большей длине!) |
относительно |
|
указанного в табл. 4-5 'благодаря использованию тривиального урав нения.
|
|
|
|
|
|
|
|
|
Т а б л и ц а |
4-5 |
||
|
Реализуе |
|
|
|
|
|
|
|
Эффектив |
|
|
|
|
|
|
|
|
|
|
|
ное |
кодо |
Кодовое |
||
Скорость |
мое рас |
|
|
|
|
|
|
|
||||
|
Порождающий |
полином |
вое |
огра |
ограниче |
|||||||
k/n |
стояние |
|
||||||||||
|
Ь |
|
|
|
|
|
|
|
ничение |
ние |
т |
|
|
|
|
|
|
|
|
|
|
|
т* |
|
|
1/3 |
4 |
{ 0 , 1 } , |
{0,2} |
|
|
|
|
7 |
9 |
|
||
1/3 |
6 |
{ 0 , 1 } , |
{0,2, |
3, |
4} |
|
13 |
15 |
|
|||
1/3 |
8 |
{ 0 , |
1, |
7 } , |
{ 0 , |
2, |
3, 4, |
6} |
20 |
24 |
|
|
1/3 |
10 |
{ 0 , |
1, |
9} |
3, |
5, |
8, |
9} |
|
30 |
33 |
|
|
|
{ 0 , |
1, |
2, |
|
|
|
|
||||
2/3 |
2 |
{ 0 , |
1}, {0,2} |
|
|
|
9 |
9 |
|
|||
2/3 |
3 |
{ 0 , |
1. |
4 } , |
{ 0 , |
2, |
7} |
|
17 |
24 |
|
|
2/3 |
4 |
{ 0 , |
8, |
9, 12}, { 0 , 6, |
11, |
13} |
31 |
42 |
|
|||
3/4 |
4 |
{ 0 , |
3, |
15, |
19}, |
|
|
|
46 |
80 |
|
|
|
|
{ 0 . |
8, |
17, |
18}, |
|
|
|
|
|
|
|
|
|
{0, |
6, |
11, |
13} |
|
|
|
|
|
|
|
JQ4
MP
ft(»> |
о |
|
0 |
||
|
*SI } |
2( 1 >, |
. z. |
,<0 |
( I ) |
A*)
(2) |
£T<2> |
/z<2> |
Л2) |
,(2> |
Z<2> |
.(2) |
i(«-«=) |
|
>r+I |
|||
|
|
r—I |
|
|
|
(ra-ft) |
|
|
|
|
, ( " - * ) |
- ( « - * ) |
|
|
-k) |
h(n-k) |
hin-k) |
"o |
" r |
zr—1 • • • z 0 |
4 n ' k ) вУ~гк) |
|
|
|
|
Например, рассмотрим |
код со скоростью |
А/ге=2/3 двоичных еди |
||||||||||||||||
ниц на выходной символ, порождаемый полиномами |
|
{0, 1} и {0, 2}, |
||||||||||||||||
т. е. G(x) = \+x, |
Н(х) = 1+х2. |
Контрольная |
матрица |
этого |
кода при |
|||||||||||||
бессиндромном декодировании (4-8) равна: |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
1 |
|
|
1 |
|
|
|
|
|
|
|
1 |
|
о |
|
о |
|
|
Н* = |
|
|
|
|
|
|
|
|
|
|
|
О |
|
1 |
|
о |
|
|
|
1 |
1 |
|
|
О |
1 |
|
|
|
О |
|
0 |
1 |
|
||||
|
|
|
|
|
|
|
|
|
||||||||||
|
М) |
- ( I ) |
Л2 ) |
„(2) . (2) |
„(2) |
„(2)s |
; |
+ |
2 |
c |
i |
c |
i |
+ i |
c |
i |
+ 2 |
|
|
|
+ l |
"4 + 2 |
*i— 2 °t—l |
|
,•+1 |
|
|
|
|
||||||||
отсюда |
получаем |
уравнения, |
с помощью |
которых |
вычисляются |
|
инфор |
|||||||||||
мационные символы s'.1) и |
s\2\ |
••о. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
,(1) _ |
с (1 ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2) |
|
, ( 2 ) : |
|
|
|
|
|
|
|
|
(2) |
|
|
|
|
Схема кодера и декодера для рассматриваемого |
кода |
показана |
||||||||||||||||
на рис. 4-6. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В |
заключение рассмотрим |
сверточные |
коды |
|
с |
|
обнаружением |
|||||||||||
и исправлением вспышек ошибок. Передача информации с помощью сверточного кода может производиться по одному каналу или по п параллельным каналам. В первом случае возникновение вспышки ошибок длины 6 означает, что на каждую из последовательностей
(имеются в виду k информационных и п—k контрольных |
последо |
||
вательностей) |
накладывается вспышка |
ошибок длиной в |
среднем |
6/л. |
при £/«=1/2 и Ь четном |
|
|
Например, |
в информационной |
последо |
|
вательности и контрольной последовательности возникнет вспышка ошибок длиной 6/2.
При этом первым искаженным символом может |
оказаться |
|
инфор |
||||||||||||
мационный |
( е | ' ' , ef\ |
е\]^и |
e j + p . . . , e j ^ 2 — 1> el+bl2—J |
и |
л " |
к о н |
т Р о |
л |
ь н ы й |
||||||
Л2 ) „0). |
|
••• • |
в |
1+6/2) символ. |
Для рассматриваемого |
случая |
|||||||||
|
«i+i> |
|
|
||||||||||||
сверточные коды с обнаружением и |
исправлением |
ошибок |
|
могут |
|||||||||||
быть построены следующим образом. |
|
|
|
|
|
|
|
||||||||
Пусть порождающий полином сверточного кода с мажоритарной |
|||||||||||||||
схемой |
декодирования |
|
ассоциирован с |
элементами |
множества |
М= |
|||||||||
"={аь |
«2,..., |
а.ц—г}, |
причем ai=0 . Тогда полином, |
ассоциированный |
|||||||||||
с элементами |
множества |
Afo={6a2/2, |
6 a 3 / 2 , . . . , |
6ajv72}, |
порождает |
||||||||||
сверточный код с коррекцией (Л'—1)/2 |
или менее независимых |
оши |
|||||||||||||
бок длины |
b |
(при декодировании |
без |
размножения |
|
ошибок) на |
|||||||||
длине |
|
|
m'=br+2-\-b{r—аг)/2 |
символов. |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|||||||
Доказательство этого факта достаточно простое. Действительно, |
|||||||||||||||
a*—ajSsl |
для любых |
|
i и /', 1ф\. |
Поэтому при умножении |
элемен |
||||||||||
тов множества М на 6/2 разность между любыми двумя |
элементами |
||||||||||||||
нз множества |
M'={6ai/2, |
6a2 /2 |
6ая/2} будет не |
меньше |
6/2 и |
||||||||||
вспышка |
ошибок |
длины |
6/2, накладывающаяся |
на |
ииформа- |
||||||||||
106
S(1\x) |
Кодер |
|
si*2 |
JO |
|
|
|
Декодер
~ l
s i - /
/772
A )
/772
S f ! V |
s (+2 |
D |
s i - 2
/772 &/Y
/772 D |
т2 |
D |
/772 |
|
|
ci*i |
|
Рис. 4-6. Схема кодера и декодера для сверточиого кода с k/n=2U, 6=3.
to
ю
•*
со
Реализуемое расстояние
00
00 |
28, |
|
|
{4, 12, |
||
|
|
•* |
|
•* |
CM |
|
|
14, |
||
|
{2,6, |
|
о |
со |
|
|
15, |
||
|
||
|
{5, |
|
|
со |
|
|
см |
|
00 |
см" |
|
|
||
•* |
со |
|
|
||
|
<м" |
|
|
ю |
|
о |
1 |
|
|
{5, |
||
|
||
00 |
см |
|
|
||
•* |
со |
|
см" |
||
|
||
|
Длина вспыш ки Ь |
Порождаю щий полином |
см
см
см
о
см
00
см
см
•*
•*
СО
00
Эффективное кодовое огра ничение т!
цпонпую |
последовательность, |
|||||||||
|
исказит |
не |
более |
одного |
кон |
|||||
|
трольного |
соотношения. |
Мно |
|||||||
|
жество |
Мо 'получается |
из М' |
|||||||
|
отбрасыванием |
первого |
элемен |
|||||||
та 6ai/2 с целью |
сдвига |
кон |
||||||||
трольной |
последовательности |
|||||||||
относительно |
|
информационной |
||||||||
на 6ai/2 разрядов. Этот сдвиг |
||||||||||
предотвращает |
|
возможность |
||||||||
одновременного |
|
|
искажения |
|||||||
двух |
контрольных |
|
соотноше |
|||||||
ний. При бессиндромном |
деко |
|||||||||
дировании |
полученного |
свер- |
||||||||
точного |
кода |
разделенные кон |
||||||||
трольные соотношения |
соответ |
|||||||||
ствуют следующим |
строкам ма |
|||||||||
трицы |
|
Н*: |
йа2 /2, |
6а3 /2, . . . |
||||||
. . . , 6ajv/2. Отсюда следует, что |
||||||||||
код исправляет (N—1)/2 или |
||||||||||
менее |
|
независимых |
вспышек |
|||||||
ошибок длины b на длине |
||||||||||
|
т?=3 |
(br/2 + 1) — 1 —Ь а 2 / 2 = |
||||||||
|
|
= й(3г — а 2 )/2+2 |
|
|||||||
символов [см. (4-9)]. |
|
|
|
|||||||
|
В табл. 4-6 приведены не |
|||||||||
которые |
параметры |
сверточных |
||||||||
кодов, |
полученных |
с |
помощью |
|||||||
описанного алгоритма |
на |
осно |
||||||||
вании кодов из табл. 4-2. |
|
|||||||||
|
В тех случаях, когда ин |
|||||||||
формационная |
|
и контрольная |
||||||||
последовательности |
передаются |
|||||||||
по отдельным |
каналам, |
причем |
||||||||
в каждом из них возможно |
||||||||||
возникновение вспышки |
ошибок |
|||||||||
длины не более Ь, сверточный |
||||||||||
код для обнаружения |
и исправ |
|||||||||
ления |
этих |
ошибок |
|
конструи |
||||||
руется |
|
следующим |
|
образом. |
||||||
Пусть, как и ранее, 'порождаю |
||||||||||
щий полином |
|
сверточного |
кода |
|||||||
с |
разделенными |
контрольными |
||||||||
соотношениями |
|
ассоциирован |
||||||||
с |
элементами |
|
множества |
|
М = |
|||||
= |
{ai, |
аг, . . . , |
|
as—г}. |
|
|
|
|||
Тогда полином, ассоции рованный с элементами множе ства {aib, агЬ, ацЬ=гЬ},
порождает сверточный код с исправлением (N—1)/2 или ме нее независимых вспышек оши бок длины b приусловии, что защитный промежуток между
108