Рейтинг@Mail.ru

Аппаратная реализация декодера свёрточного кода по алгоритму Витерби

Print Friendly, PDF & Email
Мы рассмотрели принцип кодирования и декодирования свёрточных кодов по алгоритму Витерби в предыдущей статье. Теперь опишем идею аппаратной реализации данного алгоритма (для ПЛИС).

Из пошагового описания алгоритма декодирования Витерби видно, что декодер состоит из следующих основных блоков:

  1. Генератор ветвей.
  2. Вычислитель метрик ветвей.
  3. Вычислитель метрик путей.
  4. Селектор выживших путей.
  5. Память путей.

Генератор ветвей содержит таблицу всех возможных ветвей (переходов между узлами) на одном шаге и кодовые биты, соответствующие этим переходам. Графически эти переходы представляются решёткой. В аппаратной реализации они задаются таблицей, алгоритм построения которой описан выше.

NУзелПереход в узелВыход кодера, Z4Z3Переход в узелВыход кодера, Z2Z1
00000000010011
10010001110000
20100010110110
30110011010101
41000101111000
51010100011011
61100111011101
71110110111110

Из таблицы видно, что узлы образуют устойчивые пары (000,001), (010,011), (100,101), (110,111). Пары характеризуются тем, что все ветви из пары узлов ведут в другую пару узлов и только в неё, причём каждый узел из входной пары соединён с каждым узлом из выходной пары. Например, пара узлов (010,011): ветви из узла 010 ведут в узлы 001 и 101. И из узла 011 ветви ведут в узлы 001 и 101. Легко видеть, что образующие пары узлы отличаются только значением в крайнем правом разряде. Это легко объяснимо: в соответствии с алгоритмом построения таблицы, описанным выше, следующее состояние получается из предыдущего при «дописывании» слева значений «1» или «0» и записи как следующего состояния k-1 бит начиная слева, включая дописанное значение, т.е. крайний правый бит, которым и различаются два узла, теряется. Таблица ниже иллюстрирует это:

Исходное состояниеДописать слева «0»Взять k−1 = 3 бита слеваРезультат
01000100010001
01100110011001
Исходное состояниеДописать слева «1»Взять k−1 = 3 бита слеваРезультат – следующее состояние
01010101010101
01110111011101

Выгода от выделения узлов в пары заключается в том, что для каждой пары узлов вычисления метрик ветвей и путей, проходящих через эту пару узлов, не зависят от прочих узлов. Поскольку из каждого узла выходит две ветви, и в каждый узел входят две конкурирующих ветви, и каждая пара узлов однозначно связана с другой парой узлов и только с ней, то получается «бабочка», состоящая из пары входных узлов, перечисленных в таблице, и пары выходных узлов. Узлы исходного состояния и следующего состояния всегда принадлежат только одной «бабочке». В таблице переходов каждые две подряд идущие строки, начиная с нулевой, составляют «бабочку», однозначно связывающую пару улов из второй колонки и два узла из 3 и 5 колонок.

NУзелПереход в узелВыход кодера, Z4Z3Переход в узелВыход кодера, Z2Z1
00000000010011
10010001110000
20100010110110
30110011010101
41000101111000
51010100011011
61100111011101
71110110111110

Из 8-ми узлов получается 4 «бабочки»:

Входная пара узлов «бабочки»Выходная пара узлов «бабочки»
(000,001)(000,100)
(010,011)(001,101)
(100,101)(010,110)
(110,111)(011,111)

Видно, что пары входных и выходных узлов не совпадают, но каждый узел входит только в одну входную пару и, соответственно, одну выходную пару. Графическое представление «бабочки» показано на рисунке ниже.

(000,001)-(000,100)(010,011)-(001,101)(100,101)-(010,110)(110,111)-(011,111)
Бабочки Витерби Бабочки Витерби Бабочки Витерби Бабочки Витерби
Бабочки Витерби Бабочки Витерби Бабочки Витерби Бабочки Витерби

Также видно, что если рассматривать узел как двоичное число, то пара входных узлов отличается на единицу. Отсюда очень легко получить генератор ветвей – это обычное ПЗУ, содержащее таблицу переходов. Адресом ПЗУ служат двоичные значения пары узлов. Выход ПЗУ – значения (Z04, Z03, Z02, Z01) и (Z14, Z13, Z12, Z11) – кодовые биты при переходе из чётного и нечётного узла. Такое ПЗУ изображено на рисунке ниже:

ПЗУ с таблицей переходов
ПЗУ с таблицей переходов

Содержимое ПЗУ показано в таблице:

АдресКодовые комбинации для переходов из нечётного узлаКодовые комбинации для переходов из чётного узла
B2B1B0A2A1A0Z14Z13Z12Z11Z04Z03Z02Z01
00100000111100
01101001101001
10110011000011
11111010010110

Вычислитель метрик ветвей рассчитывает хэмингово расстояние между принятой кодовой комбинацией и комбинацией, соответствующей переходу от одного узла к другому. Вычислитель состоит из схем сложения по модулю два и ПЗУ, в котором хранится таблица соответствия «комбинация – количество единиц в комбинации». Схема такого вычислителя показана на рисунке ниже.

Вычислитель метрик ветвей
Вычислитель метрик ветвей

X1, X0 – принятые биты кодовой комбинации. Z2, Z1 – биты комбинации, соответствующей переходу от одного узла к другому. По модулю два попарно складываются младшие и старшие биты.

Вычислитель метрик путей рассчитывает сумму метрик путей с учётом метрики ветви. Для одного пути представляет собой сумматор, на вход которого подается накопленная метрика пути и рассчитанная в текущем шаге метрика ветви.

Вычислитель метрик путей
Вычислитель метрик путей

M – это метрика пути, разрядность этой величины зависит от построения декодера. HD1, HD0 – двухбитное значение метрики ветви.

Селектор выживших путей сравнивает метрики двух путей, приходящих в узел, и выбирает путь с наименьшей метрикой. При равенстве метрик выбирает один из двух путей случайным или предопределенным образом (например, всегда выбирается путь из чётного узла). Представляет собой компаратор в связке с мультиплексором. На вход компаратора поступают метрики двух путей, компаратор определяет меньшую и выставляет «0» или «1» на адресный вход мультиплексора. На входы данных мультиплексора также поступают метрики двух путей, с выхода мультиплексора снимается метрика выжившего пути.

Селектор выживших путей
Селектор выживших путей

A, B – метрики двух конкурирующих путей, входящих в узел.

Память путей хранит ветви, выжившие на каждом шаге. Память может быть организована различным образом. Например, в памяти могут храниться значения узлов, составляющих путь, – так, как описывались пути выше. Недостатком такого подхода является необходимость перезаписи всей накопленной при декодировании цепочки узлов в случае гибели пути. Из рассмотренного выше примера видно, что к концу второго шага декодирования один из выживших путей был (100;010;101). Однако на третьем шаге у узла 101 не выжила ни одна ветвь из двух, а значит и путь (100;010;101) прервался. При этом у узла 100 выжили обе ветви, путь (001;000;100) разветвился на два: (001;000;100;010) и (001;000;100;110). Значит, в конце третьего шага необходимо переписать значение (001;000;100;110) (или (001;000;100;010)) в область памяти, где ранее хранился погибший путь (100;010;101). Эта операция требует дополнительных ресурсов. Поэтому в описываемой аппаратной реализации применен другой способ хранения.

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

Ниже показана таблица генератора ветвей. Рассмотрим пару узлов (010, 011), которая выделена в таблице рамкой.

NУзелПереход в узелВыход кодера, Z4Z3Переход в узелВыход кодера, Z2Z1
00000000010011
10010001110000
20100010110110
30110011010101
41000101111000
51010100011011
61100111011101
71110110111110

Для каждого узла из пары примем «1» для кодирования выжившей ветви и «0» в противном случае. Получается четыре возможных состояния ветвей узла.

Для узла 010:

СостояниеВыжившие ветви
00Исходящих из узла ветвей нет
01Выжила ветвь (010;101)
10Выжила ветвь (010;001)
11Выжили обе ветви (010;101) и (010;101)

Для узла 011:

СостояниеВыжившие ветви
00Исходящих из узла ветвей нет
01Выжила ветвь (011;101)
10Выжила ветвь (011;001)
11Выжили обе ветви (011;101) и (011;101)

Коды состояний ветвей эти двух таблиц связаны соотношение NOT. Так происходит потому, что если выжила ветвь (010;101), то ветвь (011;101) погибла: в узел может входить только одна ветвь. Значит, вторая таблица избыточна, и достаточно хранить состояние ветвей только одного из двух входных узлов в «бабочке».

Следовательно, в конце каждого шага состояние ветвей описывается комбинацией из 2k−1/2 двухбитных комбинаций, в нашем случае это будет 24−1/2 = 23/2= 8/2 = 4 двухбитных комбинации или 8 бит. Так, для конца 3 шага это состояние будет таким:

УзелСостояние ветвей
00011
01001
10011
11010

Для хранения путей потребуется ОЗУ ёмкостью 8×L бит, где L – глубина декодирования. По сути L – это номер шага и для каждого шага записывается состояние ветвей на момент окончания шага.

Такой способ кодирования может быть не очень удобен. Для восстановления пути используется обратный проход, от L к 0, в таблице же кодируются исходящие из узла ветви. Пусть на L-ом шаге произведена оценка метрик путей и выбран путь с наименьшей метрикой. Пусть этот путь заканчивается в узле 010. Прочитав из ОЗУ комбинацию, кодирующую состояние ветвей в конце L-го шага, мы не получим непосредственно значение узла, из которого был осуществлен переход в узел 010. Для получения этого значения нужно проделать некоторые операции, которых можно избежать, изменив способ кодирования.

Если посмотреть на «бабочку» со стороны выхода, то можно видеть, что в каждый выходной узел входит две ветви, по одной из каждого входного узла. При этом обязательно должна выжить одна из двух ветвей. Следовательно, можно закодировать ветвь, ведущую в текущий выходной узел из чётного входного значением «0», а из нечётного – «1». Одна из ветвей обязательно выживет и для кодирования выжившей ветви будет достаточно одного бита. Поскольку узлов 2k−1, то для описания выживших на каждом шаге ветвей потребуется 2k−1 бит, в нашем случае 2k−1 = 24−1 = 23 = 8 бит или 8×L бит для L шагов. При той же ёмкости памяти обратный просмотр пути упрощается. Для получения следующего узла при обратном проходе требуется выполнить следующие операции:

  1. Приписать справа к значению узла бит, кодирующий выжившую ветвь.
  2. Взять k−1 бит справа – это и будет номер следующего узла.

Так получается потому, что значение выходного узла содержит в себе k−2 бит входного узла – ведь выходной узел получен из входного операцией сдвига вправо с модификацией крайнего левого разряда. При операции сдвига теряется крайний правый разряд. Соответственно, входной узел может быть «восстановлен» из выходного операцией сдвига влево. При этом останется неопределенным крайний правый бит. Его легко восстановить: значение бита может быть «1» или «0», а значит, входящий узел будет чётным или нечётным. Поскольку в выходящий узел ведет две ветви, одна из нечётного узла, другая из чётного, то достаточно знания о том, какая ветвь выжила, для восстановления крайнего правого бита. Если, как указано выше, кодировать выжившую ветвь, ведущую из чётного узла значением «0», а из нечётного – «1», то этот бит и будет значением крайнего правого бита входящего узла.

Рассмотрим ветви, входящие в узел 101:

NУзелПереход в узелВыход кодера, Z4Z3Переход в узелВыход кодера, Z2Z1
00000000010011
10010001110000
20100010110110
30110011010101
41000101111000
51010100011011
61100111011101
71110110111110
Выходной узелВходной узел чётныйВходной узел нечётный
101010011

Выжить должна одна из этих двух ветвей. Если выживет ветвь, ведущая из чётного узла 010, это состояние будет закодировано значением «0». Если выживет ветвь, ведущая из нечётного узла 01, это состояние будет закодировано значением «1».

В первом случае:

  1. Дописываем справа к значению узла код выжившей ветви: 101 + 0 = 1010
  2. Берём k − 1 = 3 крайних правых бита от полученного значения 1010 = 010

Действительно, входящим узлом оказывается узел 010.

Во втором случае:

  1. Дописываем справа к значению узла код выжившей ветви: 101 + 1 = 1011
  2. Берём k − 1 = 3 крайних правых бита от полученного значения 1011 = 011

И в этом случае входящий узел однозначно восстанавливается.

Для восстановления пути требуется обратный проход по памяти путей, начиная от последнего шага до первого. В это время работа декодера может быть заблокирована, либо же дальнейший приём должен вестись с записью путей в другую страницу памяти. Этого можно избежать, если на каждом такте работы декодера считывать состояние ветвей в предыдущем проходе и сразу после этого записывать состояние ветвей в текущем проходе в ту же ячейку. В этом случае чтение из памяти осуществляется одновременно с записью в память, и адрес чтения/записи изменяется от 0 до L и далее от L до нуля. Ниже показана схема, реализующая такую логику работы.

Схема работы декодера Витерби
Схема работы декодера Витерби

Данная схема работает для глубины декодирования L=4. Такая маленькая глубина взята для наглядности. Считается, что декодирование происходит покадрово, т.е. 4 двухбитных кодовых комбинации составляют кадр, каждый последующий кадр не зависит от предыдущего.

ОЗУ в схеме работает следующим образом: по фронту тактового сигнала данные по адресу на входах A3…A0 защёлкиваются на выходах D7…D0, входные данные на входах D7…D0 записываются в ОЗУ по адресу на входах A3…A0.

На вход ОЗУ поступает восьмибитное слово состояния ветвей для каждого шага. В этом слове позиция бита в слове определяет узел (крайний левый бит D0 – узел 0002, крайний правый бит D7 – узел 1112), значение бита – выжившую ветвь, входящую в узел («0» – ветвь из чётного узла, «1» – ветвь из нечётного узла).

Адрес формируется двунаправленным счетчиком CT. Если на входе управления счётом установлено значение «0», по фронту тактового сигнала значение на выходах счётчика A3…A0 увеличивается, если на входе управления «1» – уменьшается.

Два компаратора управляют направлением счёта. Первый компаратор сравнивает значение на выходах счётчика с величиной L−1=4−1=3. При достижении этого значения на выходе компаратора появляется «1». Эта единица поступает на S-вход RS-триггера, устанавливая выход триггера в значение «1» и переключая счётчик на счёт в обратном направлении. Второй компаратор сравнивает значение на выходах счётчика с величиной 1. При достижении этого значения на выходе компаратора появляется «1», которая поступает на R-вход RS-триггера, сбрасывая выход триггера в значение «0» и переключая счётчик на счёт в прямом направлении. RS-триггер синхронный, поэтому изменения в его состоянии наступают только по фронту тактового импульса. Изменение направления счёта счётчика будет задержано на один такт, поэтому счётчик будет считать от 0 до 4 и обратно. Слова состояния ветвей будут записаны по адресам 0,1,2,3 и 4,3,2,1 соответственно (или [0,L−1] и [L,1]).

Схема на двух элементах И (один из них с инверсным входом) и элементе ИЛИ формирует сигнал прохождения L шагов (сигнал достижения глубины декодирования).

Два D-триггера осуществляют задержку сигнала прохождения L шагов на два такта: это нужно для корректной работы схемы. С выхода второго триггера снимается сигнал START_TRACE – сигнал начала обратного прохода по пути.

Мультиплексор, подключённый к выходу ОЗУ, выбирает из слова состояния ветвей состояние одной ветви, входящий в очередной узел пути. Значение узла устанавливается на адресных входах мультиплексора.

Второй мультиплексор нужен для установки узла, с которого начнется путь. На его один из его входов поступает значение узла, сформированное по сигналу прохождения L шагов, «защелкнутое» во внешнем по отношению к схеме регистре. На второй вход поступает значение очередного узла пути, получаемое в результате обратного прохода, т.е. все остальные узлы пути, кроме первого. Сигнал прохождения L шагов, задержанный на два такта, переключает выход мультиплексора так, что значение узла, с которого начнется путь, поступает на адресные входы мультиплексора выбора ветви. На следующих L−1 тактах мультиплексор выбора узла будет передавать на адресные входы мультиплексора выбора ветви значение с регистра хранения текущего узла пути.

Регистр хранения текущего пути хранит значение очередного узла пути, формируемое следующим образом: младший (крайний правый) разряд поступает с мультиплексора выбора ветви, два старших разряда – с мультиплексора выбора узла, на котором установлено значение предыдущего узла.

Декодированные биты данных считываются с выхода мультиплексора узла (старший разряд) и задерживаются на один такт в синхронном D-триггере; это необходимо, т.к. мультиплексор асинхронный и значение на его выходах достоверно только в момент прихода фронта тактового импульса.

Схема работает непрерывно, выдавая декодированные биты на каждый фронт тактового сигнала. Так как для декодирования требуется обратный проход, последний бит переданной информационной комбинации появится на L+3=7 тактовый импульс, первый бит кодовой комбинации – на L+3+(L−1)=10 тактовый импульс; биты информационной комбинации передаются из кодера в обратном порядке. После приёма последнего кадра соответствующие ему пути будут записаны в память, но выживший путь еще не будет восстановлен, поэтому потребуется еще L−1 тактовых импульсов для выдачи информационной последовательности.

Эта схема легко масштабируется в части увеличения глубины декодирования L: увеличивается разрядность счётчика, ёмкость ОЗУ и изменяется значение для первого компаратора. С увеличением количества узлов сетки будет увеличиваться разрядность слова состояния ветвей и, соответственно, ёмкость памяти и разрядность элементов части схемы, связанной с формированием значения узла.

Общая схема декодера Витерби

Генератор ветвей, вычислитель метрик ветвей, вычислитель метрик путей и селектор выживших путей объединяются в один узел-вычислитель – «бабочку». Одна «бабочка» обрабатывает одну пару входных узлов. На вход бабочки поступают принятые биты кодовой комбинации и адреса входных узлов бабочки, на выходе – две метрики выживших путей и два бита, кодирующие переход из входных узлов к выходным.

В нашем случае имеет 8 узлов, что составляет 4 «бабочки».

4 «бабочки» генератора ветвей декодера Витерби
4 «бабочки» генератора ветвей декодера Витерби

Подробная схема «бабочки» представлена ниже.

Схема вычислителя-«бабочки»
Схема вычислителя-«бабочки»

В «бабочке» появляются дополнительные регистры, хранящие память путей. Их появление вызвано необходимостью сброса буфера после завершения приёма кадра. Перед приёмом следующего кадра память путей должна быть очищена, при этом необходимо вычислить узел, на котором закончился путь с наименьшей метрикой. Эта проблема решается удвоением регистров: часть из них сбрасывается после приёма кадра, т.е. по завершению последнего шага в эти регистры вместо метрик путей записывается значение «0» и «бабочки» готовы к приему следующего кадра. В другие регистры записываются метрики путей по окончании последнего шага: эти регистры не обнуляются, и их значения используются для вычисления узла с наименьшей метрикой пути на каждом шаге. Обобщённая схема декодера показана на рисунке ниже.

Предполагается, что тактовая синхронизация в приёмнике уже достигнута. Тактовый сигнал clk_dec_high – это тактовый сигнал высокой частоты, соответствующей частоте, на которой поступают отдельные биты кодовой комбинации. Так скорость выбранного кода 1/2, одну кодовую комбинацию составляют два бита. Тактовая частота, на которой работает декодер – clk_dec_inf – в два раза меньше частоты clk_dec_high. С каждым тактом clk_dec_inf обрабатывается одна принятая кодовая комбинация, состоящая из 2-х бит.

Высокий уровень сигнала decoder_ena разрешает работу декодера. В данной реализации высокий уровень этого сигнала устанавливается по заднему фронту общего для кодера и декодера тактового генератора. Это сделано исключительно для сопряжения двух схем (кодера и декодера).

После установления высокого уровня сигнала decoder_ena импульсы тактовой частоты clk_dec_high начинают поступать в схему декодера. По фронту второго тактового импульса clk_dec_high сигнал start_decode устанавливается в высокий уровень, разрешая формирование тактовой частоты clk_dec_inf.

По каждому фронту тактовых импульсов clk_dec_inf происходит защёлкивание в двухразрядном регистре двух принятых бит кодовой комбинации, с выхода этого регистра биты кодовой комбинации поступают в «бабочки», вычисляющие метрики путей. Кроме того, по фронту первого тактового импульса clk_dec_inf устанавливается в высокий уровень сигнал mem_ena, разрешая работу блока памяти путей по второму и последующим тактовым импульсам clk_dec_inf. Сделано это потому, что запись в память слова состояния ветвей осуществляется по переднему фронту тактового импульса clk_dec_inf, однако первое такое слово будет вычислено только к моменту появления переднего фронта второго тактового импульса clk_dec_inf.

«Бабочки» обрабатывают кодовую комбинацию асинхронно. Сразу после поступления на их входы кодовой комбинации начинается процесс вычислений. К моменту появления заднего фронта тактового импульса clk_dec_inf вычисления будут закончены, и по заднему фронту их результат будет «защёлкнут» в соответствующих регистрах.

Схема на счётчике и компараторе вырабатывает сигнал clr_buf. Этот сигнал устанавливается в высокий уровень по фронту каждого четвёртого тактового импульса clk_dec_inf и сбрасывается в 0 по фронту следующего тактового импульса. К моменту завершения вычислений в «бабочках», т.е. к моменту появления заднего фронта тактового импульса clk_dec_inf, этот сигнал уже установлен.

Сигнал clr_buf отвечает за сброс регистров, хранящих метрики путей в «бабочках». При этом сбрасываются только те регистры, выходы которых подключены к «бабочкам». Регистры, подключенные к схеме поиска узла, в котором закончился путь с наименьшей метрикой, не сбрасываются.

Схема поиска узла, в котором закончился путь с наименьшей метрикой – асинхронная. По заднему фронту тактового импульса clk_dec_inf новые значения метрик путей «защёлкиваются» в регистрах «бабочек», данные с них поступают в схему поиска узла и в ней начинается процесс вычислений. Он заканчивается к моменту появления переднего фронта следующего тактового импульса clk_dec_inf. Если в этот момент происходит переход сигнала clr_buf из высокого состояния в низкое (принят кадр, составляющий 4 кодовых комбинации) – найденный узел «защёлкивается» в регистре хранения.

Работа схемы блока памяти путей описана выше.

Рассмотрим работу схемы при декодировании принятой кодовой комбинации 111110002. Приём бит кодовой комбинации осуществляется по передним фронтам тактовых импульсов clk_dec_high. По каждому второму тактовому импульсу clk_dec_high из двух последовательно принятых бит кодовой комбинации формируется двухбитная кодовая комбинация в параллельном коде; на диаграммах сигналов ей соответствует сигнал coded_in. Принятые кодовые комбинации показаны на рисунке ниже. Сигнал coded_bit – последовательно передаваемые биты кодовой комбинации, coded_in – они же, преобразованные в параллельные двухбитные кодовые комбинации.

Формирование декодером выходного сигнала
Формирование декодером выходного сигнала

При этом диаграмма сигналов следующая:

Выходной сигнал декодера
Выходной сигнал декодера

Процесс декодирования кодовой комбинации 111110002 был детально описан выше. На рисунке ниже показаны выжившие на каждом шаге декодирования пути. В таблице под рисунком записаны слова состояния ветвей в соответствие с принятой в декодере системой кодирования (0 – выжила ветвь из чётного узла, 1 – выжила ветвь из нечётного узла).

Шаги формирования выходного сигнала декодера Витерби
Шаги формирования выходного сигнала декодера Витерби
ШагУзел
111110101100011010001000
101000001
201000001
310000010
400010100

Слова состояния ветвей начинают вычисляться в «бабочках» по переднему фронту каждого тактового импульса clk_dec_inf. По заднему фронту эти слова «защёлкиваются» в регистрах «бабочек». Каждая бабочка отвечает за два выходных узла, соответственно, на выходе «бабочки» имеется два бита из слова состояния ветвей. Эти двухбитные выходы объединяются в восьмибитное (по числу узлов) слово состояния ветвей code_mem. По переднему фронту следующего тактового импульса слово состояния ветвей записывается в память блока путей.

Очередная кодовая комбинация на входе «бабочки»
Очередная кодовая комбинация на входе «бабочки»

Видно, что вычисленные слова состояния ветвей code_mem совпадают с указанными в таблице. Эти слова записываются в адреса памяти блока путей 0…3. После приёма 4-й кодовой комбинации, по фронту 4-го тактового импульса clk_dec_inf устанавливается строб очистки регистров «бабочек» clr_buf. По заднему фронту 4-го тактового импульса clk_dec_inf регистры путей в «бабочках», выходы которых подключены ко входам «бабочек» будут сброшены. Регистры, хранящие коды выживших путей, сброшены не будут. Также не будут сброшены регистры, хранящие метрики выживших путей, и подключённые к блоку вычисления узла, в котором закончился путь с наименьшей метрикой.

Поиск узла, в котором закончился путь с наименьшей метрикой (стартового узла для обратного просмотра) осуществляется непрерывно. Найденный узел «защёлкивается» в регистре по заднему фронту строба clr_buf.

Диаграмма поиска узла пути с наименьшей метрикой
Диаграмма поиска узла пути с наименьшей метрикой

Материал прислал наш читатель под псевдонимом MIL1553.

Заключение

Предложенная схема построения декодера не является оптимальной и иллюстрируется подход к его аппаратной реализации. Так, работа по переднему и заднему фронтам снижает максимальную частоту, с которой может работать схема: если бы метрики путей и коды ветвей «защёлкивались» по переднему фронту, максимальная частота работы схемы была бы выше в два раза. Функции схемы очистки регистров бабочек и переключения направления счёта в блоке памяти путей дублируют друг друга. Решение с удвоением количества регистров в «бабочке» не самое изящное.

Метрики путей хранятся в регистрах большой разрядности. Этого можно избежать, если на каждом шаге декодирования модифицировать метрики. Для работы декодера не нужны абсолютные значения метрик, важно лишь сохранение отношений между ними. Поскольку метрики путей вычисляются на каждом шаге, и находится минимальная из них; на следующем шаге это найденное минимальное значение можно вычесть из ВСЕХ метрик путей. Таким образом можно сэкономить на разрядности регистров и сумматоров.

Нет необходимости использовать для идентификации «бабочки» оба входящих в неё узла, можно ограничиться номером чётного узла или же номером «бабочки»; это уменьшит требования к ПЗУ.

Если имеется значительный запас по частоте, нет необходимости реализовывать «бабочки» как параллельные вычислительные блоки. Поскольку «бабочки» работают независимо друг от друга и отличаются только кодовыми комбинациями, получающимися при переходе из входных узлов «бабочки» в выходные, можно реализовать последовательную обработку с высокой частотой.

Кодер реализован упрощенно, обычно разрядность сдвигового регистра выбирают равной k−1, старший разряд защёлкивается в регистре во внешнем по отношению к кодеру триггере.

- MIL1553
Последнее изменениеСреда, 23 Март 2022 20:34 Прочитано 531 раз

Поделиться

Print Friendly, PDF & Email

Оставить комментарий