Выходное устройство декодера витерби

 

Изобретение относится к вычислительной технике. Его использование в цифровых системах передачи информации сверточным кодом, содержащих декодер Витерби, обеспечивает упрощение устройства. Выходное устройство декодера Витерби содерямт блок 1 памяти , буферный и выходной регистры 3, 4 и блок 5 синхронизации. Благодаря введению мультиплексора 2 частично совмещаются функции адресации памяти решений и упорядочения выходных символов, что и позволяет упростить устройство. 4 ил. с (Л

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) SU (11) (51) 4 Н 03 M 13/12

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 39 74406/24-24 (22) 04.11.85 (46) 15.01.88. Бюл. № 2 (7l) Львовский политехнический институт им. Ленинского комсомола (72) В. P. Кравцов, А.,В. Моисеев, М. Ш. Розенблат и Ю. И. Сидорчук (53) 621.394.14(088.8) (56) Некоторые вопросы теории кодирования, /Под ред. Э. Л. Блоха и

М. С. Пинскера, M.: Мир9 1970, с. 142-165.

Витерби А. Д. Омура Дж. К. Принципы цифровой связи и кодирования.

M. Радио и связь, )982.

Патент США ¹ 3789360, кл. Н 04 L 1/10, 1974, фиг. 12. (54) ВЫХОДНОЕ УСТРОЙСТВО ДЕКОДЕРА

ВИТЕРБИ (57) Изобретение относится к вычислительной технике. Его использование в цифровых системах передачи информации сверточным кодом, содержащих декодер Витерби, обеспечивает упрощение устройства. Выходное устройство декодера Витерби содержит блок 1 памяти, буферный и выходной регистры

3, 4 и блок 5 синхронизации. Благодаря введению мультиплексора 2 частично совмещаются функции адресации памяти решений и упорядочения выходных символов, что и позволяет упростить устройство. 4 ил. сО

1367165

"= "1

5 где элементы вектора Т = t 1 при1 1 нимают значения 0 или 1;

= 0,2" — 1 — порядковый номер элемента (соответственно порядковый номер сдвигового регистра в блоке 1

10 памяти); порядковый номер вектора.

По окончании операции ввода данных в блок 1 кроме вновь поступивших I векторов сохраняется еще и В ранее на1Г копленных векторов, т.е. (2) Изобретение относится к вычисли" тельной технике и может быть использовано в цифровых системах передачи информации, использующих сверточный код и содержащих декодер Витерби.

Цель изобретения — упрощение устройства.

На фиг. 1 изображена функциональная схема выходного устройства декодера Витерби; на фиг. 2 — пример выполнения блока синхронизации; на фиг. 3 — временные диаграммы работы блока синхронизации; на фиг. 4 — пример восстановления отрезка выходной последовательности при кодовом ограничении К = 3.

Выходное устройство декодера Витерби содержит блок 1 памяти, мультиплексор 2, буферный регистр 3, ре- 20 гистр 4, блок 5 синхронизации, входы

6 и выход 7.

Блок 1 памяти предназначен для хранения частных решений о переходах между состояниями декодера Витерби и 25 к- может быть выполнен на 2 реверсивных сдвиговых регистра 8 состоящих из В + L разрядов каждый, где В— число выходных символов декодера, полученных ранее, L — - число выходных 30 символов декодера, полученных в процессе восстановления пути по данным, извлекаемым из памяти. Регистры 3 и

4 имеют каждый по L разрядов.

Блок 5 синхронизации для случаев

В = L = 15 выполнен (фиг, 2) на гене.раторе 9 тактовых импульсов, счетчике 10 по модулю три, счетчике 11 по модулю пять, первом и втором триггерах 12 и 13 и элементе И 14, На 40 фиг. 2 обозначены выходы 15-18 блока

5 с первого по четвертый соответственно, На фиг. 3 буквами а-д обозначены сигналы в соответствующих точках блока 5 (фиг. 2).

Выходное устройство декодера Витерби работает следующим образом.

Каждый цикл работы устройства (как и в прототипе) разбивается на три равных временных интервала. На пер50 вом интервале m-ro цикла на управляющем входе блока 1 памяти находится нулевой потенциал (фиг. Зг) и из вычислителя метрик декодера на входы

6 в блок 1 памяти в естественном по55 рядке поступает m-ый набор из L векторов частных решений о переходах между состояниями декодера ((+ ) (mL <(.-Il

Ф ф ° ° 4 ф

) с (m(-М (4(.-8- ) (т (.-<)

Т Т,...,Т (m(+i) (rnL+L -i) т; Т,...,Т

В остальное время m-го цикла на управляющем входе блока 1 памяти находится единичный потенциал (фиг. 3г) и порядок следования данных в регистрах 8 блока 1 инверсный. Векторы последовательности (1) поступают из блока 1 в следующем инверсном порядке. с (m(,i I,-i) (m(+ I) (my)

Т,...,Т ., т (m1.-() ((, )

Т,...,Т

) т.е. первым извлекается вектор (гр 1. - I )

Т("; поступивший последним в блок 1 на первом временном интервале цикла, Последовательность (2) перезапоминается, и в конце цикла ее элементы 1) располагаются на исходных позициях в блоке 1 памяти.

По последовательности (2) с помощью мультиплексора 2, работающего в качестве схемы выборки решений, восстанавливается один из 2 возможных отрезков длиной В + L символов. В (2) рекомендуется выбирать глубину поиска решений.В в пределах (4-6)К, в этом случае у любых возможных отрезков пути длиной В + Ь символов совпадают, Следовательно, L последних символов восстановленного отрезка пути практически равны соответствующим символам оптического пути.

По окончании цикла L последних символов восстановленного отрезка пути пересылаются из буферного регистра 3 в регистр 4, Порядок следования данз 136 1 ных в регистре 4 — инверсный по отношению к буферному регистру 3 °

В устройстве для адресации содержимого блока 1 памяти используется

5 содержимое первых К-1 разрядов буферного регистра 3. Такая возможность частичного совмещения функций адресации памяти решений и упорядочения результатов следует из определения 0 частных решений. Действительно, согласна алгоритму (2) независимо от номера итерации частные решения с порядковыми номерами 2 J и 2 g + 1 к-г зависят от значений метрик М и M +

+,) и приращений метрик h + Я

3 2" ) 1

К2 которые относятся к )-му и (2 +

+j )-му состояниям декодера

20

0ф если М + h М „, . +r) кг .

) ) 2к-2 2к гФ у если M> + Q w М2„.z 92K-г

2к + 2 11 25 (3) если М; + A, М кz ° + )(2

0, т

2) 1

1, (mL<(>) 0,, = О, (го Ь 4 L " ""> ) 1э 01 Iý (mL+ L-1) Oв (mL+ L-6)

01 («1L+ ).-4)

10 („(, + L-г)

1О если М +9(к,.<М к 4 )(2К-2 °

Из примера видно, что старший (младший) разряд (i + 1)-го адреса

З5 памяти решения совпадает с i-ым ((i1)-ым соответственно) символом B6l ходной последовательности. Так, третий, четвертый, пятый и шестой адреса равны

40 (r«L i L -3)

10 (1«1 4 L 2)

Э 10 У (rn L t L - Э)

9 01 1 (1«L+L-4)

45 (r«L+ L -4)

10 (тЬ+1 -5)

В нредлагаемом устройстве, в отличие от прототипа, функции адресацйи памяти решений и упорядочения выходных символов частично совмещены. При условии L >z К-1, которое выполняется

55 на практике, не требуется отдельного блока памяти для формирования адреса памяти решений, как в прототипе, благодаря чему и упрощается устройство. гдето =0,2- — 1.

Из (3) следует, частное решение (либо t2 „) равно нулю единице

) +1 если предпочтительнее g-e (2 +

+ J)-e состояние декодера. Иначе . значение частного решения t (либо

2(t,, ) равно старшему разряду двоичного представления порядкового номера предпочтительного состояния декодера. Если на i-ом шаге процедуры восстановления выходной последоваI тельности декодера прочитанное из ((.+6- ) блока 1 значение t „ равно нулю (единице), то очередной символ должен быть равен нулю (единице соот" ветственно), т.е, совпадает с част(г«L 6- )

mm решением 1 „ а адрес содержимого блока 1 памяти íà (i+1)-ом

mare должен стать равным (— 1 — 1 + к-2

+ 2 соответственно). Значит, старший разряд двоичного представления («1(.4(.- ): адреса равен частному решению t „ и совпадает с очередным символом, поступающим в буферный регистр 3 на

i-ом шаге, следующий разряд адреса равен частному решению, поступившему в буферный регистр 3 Hà (i-1)-ом шаге, и т.д, Таким образом, адрес содержимого блока 1 равен содержимому первых К-1 разрядов буферного регистра 3.

Процедура восстановления выходной последовательности декодера при кодовом ограничении К = 3 иллюстрируется численным примером, представленВ ным на фиг. 4. Здесь в квадратах указаньг.значения элементов векторов (mL.L- ) частных решений Т (i = 1,6), (mLi L-r) при частном решении 1.

1 (r«Lw L-() (t; = О); переходы обозначены сплошной (соответственно, пунктирной) линией; восстановленный отрезок последовательности, выделенный сплошной линией со стрелкой, состоит иэ элементов (mL+1.-г) («(+L- )

01 = t10 1„

17

Фиг. 2

Фиг.З

5 136

Кроме минимальных аппаратурных затрат, стоимости, числа связей, габаритов и высокой надежности предлагаемое устройство характеризуется высокой степенью параллелизма, что особенно важно для декодеров с кодовыми ограниченияьк К 8.

Формула изобретения

Выходное устройство декодера Витерби, содержащее блок памяти, информационные входы которого являются одноименными входами устройства, буферный регистр, выходы которого соединены с соответствующими информационными входами регистра, и блок синхронизации, первый выход которого

6 подключен к входам синхронизации блока памяти и буферного регистра, второй — четвертый выходы блока синхронизации соединены соответственно с управляющим входом блока памяти, с управляющим входом и входом синхронизации регистра, выход которого является выходом устройства, о т л и— ч а ю щ е е с я тем, что, .с целью упрощения устройства, в него введен мультиплексор, выходы блока памяти соединены с соответствующими информационными входамн мультиплексора, выход и управляющие входы которого подключены соответственно к информационному входу и первому (К-1)-му выходам буферного регистра, где К— кодовое ограничение.

7 . @ 766 ФЩ ф 1 Ф4) у(а&К) у(аЖ-ф ((ай+(-ф

Составитель О. Ревинский

Редактор С. Лисина Техред Л. Сердюкова Корректор С. Черни

Заказ 6850/55

Тираж 928 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4