Содержание к диссертации
Введение
1 Анализ методов помехоустойчивого кодирования 14
1.1 Основные понятия кодирования сигнала 14
1.2 Основные характеристики низкоплотностных кодов 18
1.3 Алгоритмы декодирования низкоплотностных кодов 22
1.3.1 Декодирование с использование алгоритма с инверсией бита 22
1.3.2 Декодирование с использованием алгоритма итеративного распространения доверия 25
1.3.3 Быстрое декодирование с использованием алгоритма min-sum 30
1.3.4 Выбор алгоритма декодирования для дальнейшей разработки LDPC-декодера 33
1.3.5 Анализ точности данных при LDPC декодировании 34
1.4 Особенности реализации LDPC-декодеров на ПЛИС 37
1.4.1 Архитектура декодера для эмуляции 39
1.4.2 Архитектурные компоненты устройств ПЛИС 40
1.4.3 Метод модельно ориентированного подхода для проектирования на ПЛИС 44
1.5 Выводы 47
2 Проблемы проектирования различных архитектур LDPC декодеров на ПЛИС 48
2.1 Полностью параллельная архитектура LDPC-декодера 50
2.2 Архитектура многоуровневого LDPC –декодера 52
2.3 Проблемы проектирования LDPC-декодеров с частично параллельной архитектурой на ПЛИС 58
2.3.1 Организация модифицированной структуры частично параллельного декодера 58
2.3.2 Оптимизация системы памяти для реализации LDPC-декодера на основе ПЛИС 63
2.3.2.1 Упаковка сообщений и выравнивание 65
2.3.2.2 Метод передачи векторных перекрывающихся сообщений 68
2.3.2.3 Метод виртуализации блоков ОЗУ для реализации LDPC-декодера на основе ПЛИС 72
2.4 Выводы 73
3 Аппаратное проектирование для программируемых частично параллельных LDPC-декодеров 76
3.1 График параллелизма и декодирования 76
3.2 Проектирование блоков обработки узлов 79
3.2.1 Проектирование блока обработки переменных узлов (VN) 79
3.2.2 Проектирование блока обработки проверочных узлов (СN) 80
3.2.3 Гибкие блоки обработки проверочных узлов (СN) 81
3.3 Реализация универсального параметризированного частично параллельного LDPC-декодера 83
3.3.1 Структурная схема декодера 83
3.3.2 Алгоритм реализации LDPC-декодера на ПЛИС 86
3.3.3 Проверка производительности и ресурсоемкости разработанного LDPC-декодера 91
3.4 Выводы 92
4 Разработка методики проектирования LDPC-декодеров на базе ПЛИС 94
4.1 Методика проектирования частично параллельных низкоплотностных декодеровна ПЛИС 94
4.2 Результаты реализации 98
4.3 Выводы 99
Заключение 101
Список литературы 103
Приложение А. Акты внедрения результатов диссертации 114
- Основные характеристики низкоплотностных кодов
- Архитектура многоуровневого LDPC –декодера
- Алгоритм реализации LDPC-декодера на ПЛИС
- Методика проектирования частично параллельных низкоплотностных декодеровна ПЛИС
Основные характеристики низкоплотностных кодов
Код LDPC представляет собой линейный блоковый код, который определяется посредством mn разреженной матрицей проверки на четность H. N обозначает количество битов в кодовом слове (или блоке), и m – число проверок на четность. Матрица, определяющая код LDPC должна быть разряженной, что предполагает низкую плотность единиц, также е основной особенностью является малая плотность значимых элементов. Она также должна быть большой. Спецификой LDPC кода является разреженная проверочная m n матрица H, пример которой приведен на рисунке 1.4, эта матрица также называется матрицей проверки на четность.
Большая доля информационных бит может привести к большей пропускной способности, впрочем, частота ошибок выше из-за отсутствия избыточных (проверки четности) битов.
Существуют регулярная и нерегулярная низкоплотностные матрицы проверки на четность. Регулярные матрицы состоят из одинакового числа «1» в каждой строке и одинакового числа «1» в каждом столбце. Нерегулярные матрицы имеют свободную структуру. Заметим, что нерегулярные конструкции кодов гарантируют наиболее высокую помехоустойчивость, нежели регулярные из-за так называемого «эффекта волны», если наиболее защищенные символы, за которыми находится больше «1» в столбце матрицы проверки на четность, быстрее других декодируются и «помогают» менее защищенным символам [22, 23].
Пример на рисунке 1.5 показывает принцип для простой матрицы LDPC. Строки М (здесь 4) означают количество проверок четности, в то время как N столбцов (здесь 6) выступают как биты для обработки через проверку. Единица на пересечении означает, какие биты будут участвовать в проверке четности, в то время как 0 означает биты, которые не участвуют в проверке. Для проверки четности 1 мы видим, что биты 1, 3 и 4 обрабатываются, поэтому их сложение в режиме двоичной арифметики должно давать ноль в случае правильного кодового слова.
Двудольный граф в правой части рисунка – графическое представление матрицы проверки на четность LDPC и называется представлением в виде графа Таннера. Нижние вершины присваиваются каждому биту в блоке кода, в то время как верхние вершины замещают проверки четности [24 – 27]. Каждая стрелка на графе является визуальным представлением единицы в проверочной матрице, показывающей, какие проверки на какие биты влияют.
Систему связей между переменными VN и проверочными CN узлами задают ребра графа. Число ребер, выходящих из данного узла, определяет степень узла. При кодировании и декодировании низкоплотностного кода для получения оптимальных результатов нужно избегать циклов, которые могут возникать в графе Таннера. Цикл представляет собой последовательность подключенных узлов, началом и концом которых является один и тот же узел на графике, который содержит более одного ребра. Длиной цикла является количество содержащихся в нем ребер, а обхват графа - это размер его наименьшего цикла.
В аппаратной реализации, каждый бит в кодовом блоке LDPC декодера отображается на переменный узел (VN), во время проверки четности, отображаются на проверочный узел (CN).
Установлено то, что процесс работы декодера LDPC-кода хуже, если в графе Таннера LDPC-кода существуют циклы небольшой длины. Обычно, циклы длины 6 не проявляют значимого воздействия на свойства декодирования, по этой причине имеющиеся на сегодняшний день модели обязаны учесть отсутствие циклов длины 4. С целью этого предостаточно, чтоб каждые два столбца проверочной матрицы LDPC-кода не содержали более одной общей отличной от нуля позиции.
Скорость блочного кода задается с учетом того, что N-K = rank 2 (H), (1.2) где N - общее количество бит в кодовом слове, К - количество информационных бит в сообщении, rank2 (H) - количество линейно-независимых строк в H над полем GF (2), определяется как для нерегулярного, если матрица проверки на четность имеет полный ранг, т.е. гап2Н), где m - количество строк в матрице.
Используя сравнения полученных векторов с любым другим кодовым словом, исправление ошибки в коде гарантированно возвращает наиболее вероятное кодовое слово. Но такой поиск возможен только при небольшом количестве бит. Для кодов с количеством информационных бит около тысячи, данный метод становится сложным, так как сравнивать полученный вектор с каждым из двух кодовых слов в коде не просто.
Было принято решение сделать эту задачу менее затратной, то есть использовать структуры, ускоряющие декодирование или, что касается LDPC кодов, получить методы декодирования, не являющиеся максимально вероятностными, но способными работать очень хорошо с гораздо меньшей сложностью. Класс алгоритмов, которые используются для декодирования низкоплот-ностных кодов, относится к семейству алгоритмов передачи сообщений (Massage passing), поскольку их работа может быть объяснена передачей сообщения по вершинам графа Таннера. Каждый узел работает независимо, имея доступ только к сообщениям на вершинах, связанных с этим узлом. Все без исключения методы декодирования LDPC кодов считаются итеративными и строятся по критерию максимума апостериорной вероятности (от англ. maximum a-posteriori, MAP). Итеративное декодирование подразумевает такое декодирование, где сообщения передаются туда и обратно между переменными (VN) и проверочными (CN) узлами итеративно, пока не будет достигнут результат, или до остановки процесса выполнения с последовательным уточнением результата на каждом этапе. Также используются различные модификации данного алгоритма, имеющие меньшую сложностью реализации. В основе работы данных методов лежит обмен мягкими решениями по итерациям между символьными и проверочными узлами графа кода. В том случае, когда на графе отсутствуют циклы, применение такого способа декодирования позволяет получить оптимальное решение.
Такими методами являются наиболее часто используемые алгоритмы инверсии битов (bit-flipping algorithm), суммарного произведения (sum-product algorithm) и алгоритм минимальной суммы (min-sum algorithm).
Архитектура многоуровневого LDPC –декодера
Многоуровневые архитектуры были предложены первыми в [54] с основной целью сокращения требуемых бит памяти. В случае многоуровневого декодера для двух типов сообщений требуется память: сообщения апостериорного отношения правдоподобия (от англ. A Posteriori Logarithmic Likelihood Ratio, AP-LLR) и сообщения контрольного узла. Архитектура многоуровневого декодера LDPC, изображенного на рисунке 2.4, содержит следующие компоненты:
1. Блоки обработки. Обработка в многоуровневом планировании состоит из вычисления сообщений переменного узла, вычисления сообщений контрольного узла и обновления AP-LLR. Сообщение переменного узла вычисляются из сообщения AP-LLR и сообщения контрольного узла. Сообщение контрольного узла вычисляется так же, как и в последовательной архитектуре, в то время как AP-LLR обновляется от новых значений переменного узла и сообщений контрольного узла. Поскольку сообщения не требуют маршрутизации между обрабатывающими узлами, то для обработки используется комбинированный блок – блок проверки переменной. Количество блоков обработки в типичном многоуровневом декодере равно числу строк, которые составляют один слой, который обычно задается размером циркулянта. Комбинированный блок содержит сумматор для выполнения вычисления переменных сообщений, буфер FIFO (First –In First-Out – FIFO), используемый для маршрутизации обновленного сообщения переменного узла в об-новлнный AP-LLR, компаратор для обновления сообщения контрольного узла и блок для обновления AP-LLR [55-57]. В памяти с последовательным доступом данные располагаются в последовательном порядке, образуя очередь. Память FIFO организуется в виде буфера. В FIFO, как правило, используется способ продвижения данных к выходу в порядке очереди, как в сдвигающих регистрах. Особенность функции FIFO является то, что запись и считывание данных осуществляется по двум различным управляющим входам и может вестись с различными скоростями. Буферы имеют средства индикации, информирующие о его состоянии: буфер полон или буфер пуст. Одно из применений буферов FIFO – организация очереди команд. При выполнении программы значительное время расходуется на выборку команд из внешней оперативной памяти. Конкретная оптимизация ПЛИС может быть реализована в комбинированном процессоре, который включает использование 6-входного LUT в CLB для реализации компаратора - компаратор реализован как память ROM [56], а также использование специализированных цепочек сдвиговых регистров для осуществления FIFO. Блок обработки имеет входы dc AP-LLR-сообщения и dc сообщения контрольного узла и выходы dc обновленных сообщений AP-LLR и dc обновленные сообщения контрольных узлов. Важным параметром для всей архитектуры декодирования является степень параллелизма на уровне блока контроля переменной, которая представляет количество сообщений AP-LLR, обрабатываемых каждым тактовым циклом (максимальная степень параллелизма равна dc). Более высокая степень параллелизма требует одновременного чтения / записи AP-LLR, а также маршрутизации, что приводит к увеличению количества портов памяти или банков памяти и переключателей для маршрутизации [58].
2. Блоки памяти. Многоуровневые декодеры требуют хранения двух ти пов сообщений: AP-LLR и сообщений контрольных узлов. AP-LLR представляют собой сообщения, которые маршрутизируются между различными процессорными блоками между обработкой уровня. Сообщения контрольных узлов относятся к каждому процессору: они не требуют маршрутизации от одного процессора к другому между разными слоями. Следовательно, память AP-LLR является общей глобальной памятью, в то время как память сообщений контрольного узла является локальной для каждого блока обработки. Что касается памяти AP-LLR, слово памяти для каждого банка имеет quant(y), а максимальная глубина этой памяти равна числу столбцов в базовой матрице. Что касается реализации BRAM-памяти AP-LLR, недостатком является низкое использование встроенной блочной памяти. Что касается сообщений контрольного узла, используются два варианта их хранения: несжатая форма, когда -сообщения в двоичном формате и сжатая форма [58]. Сообщение сжатого контрольного узла основано на том факте, что сообщения dc -1 в строке, соответствующей строке в матрице проверки на четность, имеют одинаковую абсолютную величину, равную минимуму -сообщений, подключенных к соответствующему блоку контрольного узла, тогда как абсолютное значение сообщения dc контрольного узла равно второму минимуму. Следовательно, может использоваться сжатое сообщение проверочного узла, состоящее из знаков, первого минимума, второго минимума и индекса первого минимума. Что касается реализации ПЛИС, сжатая форма подходит для реализации на основе сдвигового регистра в традиционной логике CLB, а несжатая форма подходит для реализации BRAM. Однако при реализации сообщения контрольного узла на основе BRAM память в сжатой форме предлагается для многоуровневого декодера с последовательной обработкой на уровне узла обработки. Маршрутизация из блоков BRAM, содержащих сообщения контрольного узла, в обрабатывающих блоков достигается с помощью больших регистров сдвига.
3. Маршрутизирующая сеть. Сеть маршрутизации реализуется с использованием переключателей. Количество переключателей зависит от степени параллелизма в блоке обработки. Для каждого входа AP-LLR блока обработки требуется пара переключателей - одна для маршрутизации считанных сообщений и одна для маршрутизации обновления сообщения, необходимых для записи.
4. Блок управления. Блок управления отвечает за создание адресов чтения / записи для двух запоминающих устройств, сумм сдвига для переключателя, а также сигналов управления, соответствующих блокам обработки. Тип памяти ROM используется для встраивания информации кода LDPC, из которой вычисляются адреса памяти, а также суммы сдвига.
Основная проблема многоуровневой архитектуры представлена опасностями данных. В зависимости от LDPC кода опасности данных с последующей записью могут повлиять на обновление AP-LLR: обновленное значение AP-LLR не будет записано в память до того, пока оно не будет прочитано для новой обработки слоя [59]. Проблема опасностей данных усугубляется использованием ступеней конвейеризации как в переключателе, так и в блоках обработки.
Алгоритм реализации LDPC-декодера на ПЛИС
При реализации LDPC-декодера на ПЛИС использовался САПР фирмы Xilinx ISE Design Suite, а также языки описания аппаратуры Verilog и SystemVerilog. Среда ModelSim использовалась для симуляции и отладки программ. Данное программное обеспечение (ПО) выбрано из-за удобства и простоты использования, так как язык VHDL требует трудоемких затрат на его изучение и неудобен для реализации, а другие средства отладки не удобны для изучения характеристик декодера.
Далее моделируется только лишь декодер, по этой причине закодированный сигнал, который проходит канал связи, отфильтровывается и демодулируется. С демодулятора (rx) на вход поступает восьмибитное число, а также тактовый сигнал с заданной частотой. Регистрирует начало выполнения сигнал sop, а окончание поступающей последовательности сообщает сигнал eop, также эти два сигнала регулируют работу системы в целом, то есть запускают разрешающий сигнал (val) (Рисунок 3.7). Для того, чтобы использовать входные данные в дальнейшем, их необходимо записать в оперативную память ram_idata.
Здесь минимум по строке выступает первое значение (Рисунок 3.9), а вторым значением выступает предыдущее значение минимума, для исключения значения элемента строки, который соответствует минимальному значению (Рисунок 3.10).
Для этого была создана матрица sign_matr, которая хранит в себе сигнал sign [84, 85]. Результирующей матрицей будет LQi (Рисунок 3.10), которая получается из следующих соображений:
1) Используется значение min_a по строке, умноженное на значение знаковой матрицы, если элементы модуля не равны минимуму.
2) Для вычисления используется значение min_b по строке, умноженное на значение знаковой матрицы, если элементы модуля равны минимуму.
Следующим шагом для вычисления по алгоритму min-sum является суммарное значение отношения правдоподобия (summ_LQi).
Так как min-sum является итерационным алгоритмом, то необходим перерасчет входных данных для перехода на следующую итерацию. Для этой цели в блок памяти FIFO записывается матрица LQi, значения сигналов записи и чтения регулируют разрешающий сигнал для следующей итерации. Этот сигнал позволяет приступить блоку к работе на последующих этапах декодирования. Чтобы перейти на следующую итерацию необходимо рассчитать разности (razn_lqi) между summ_LQi и LQi. Этот процесс называется пересчетом входных значении LLR. Эти расчеты производятся в блоке декодирования на первой итерации и на последующих итерационных блоках.
Подводя итог реализации итерационного алгоритма для сохранении заданной скорости входного потока требуется столько новых модулей, сколько выполняется итераций. На все декодеры, кроме первого, на вход будет поступать матрица razn_lqi. Декодированные биты сообщения со всех итерации будут поступать на выходное устройство, в связи с чем, можно проследить за работой системы и усовершенствовать ее на каждой итерации.
Другой способ реализации итерационного алгоритма требует столько же ресурсов, что и предыдущий, но уступает в скорости, основан на использовании обратной связи во втором блоке декодирования – выходные данные будут поступать на вход каждую новую итерацию.
На рисунках 3.13 – 3.15 приведено поведенческое моделирование на Modelsim. Используется тактовый сигнал clk2x с периодом 8 нс для моделирования. И используются две фазы, 0 и 180, этих тактовых сигналов. Data_transmitted -это последовательное сообщение LLR в качестве входа декодера, а reset_ctrl - это сигнал сброса для декодера. Sign_lv128 является признаком Lv. Он генерирует каждый столбец блока. С начала моделирования 4096 знаков Lv отправляются в 32 группах, и каждая группа имеет длину 128 бит. Когда блок жестких решений завершает итеративное декодирование, сигнал is_first будет установлен в «1» для одного столбца блока, то есть 10 тактов. Final_fer и final_ber - это ошибка кадра и ошибки бит, соответственно. На рисунке 3.13 показано начало моделирования, когда все последовательные входные данные загружаются в декодер. Требуется 32780 нс, то есть 4097 тактов для последовательного параллельного процесса для всех сообщений 4096. На рисунке 3.14 показано количество бит-ошибок второй последней итерации. И на рисунке 3.15 показана сходимость последней итерации. Требуется 2560 нс, т. е. 320 тактов для одной итерации.
Методика проектирования частично параллельных низкоплотностных декодеровна ПЛИС
Предлагаемый поток проектирования автоматически генерирует все файлы HDL, необходимые для реализации LDPC-декодера, имеющего гибкость во время выполнения по набору из одной или нескольких матриц проверки четности, выбранных пользователем. Этот поток проектирования включает в себя извлечение ключевых параметров и значений из набора матрицы проверки четности, создание оптимизированных структур блока обработки узла и автоматическое создание надежного описания HDL, из которого можем затем синтезировать аппаратное обеспечение. Блок-схема, изображающая этот проектный поток, представлена на рисунке 4.1.
1) Объяснение матрицы проверки четности. Прежде чем, HDL код предлагаемой модели может быть сгенерирован, требуется небольшое количество автономных вычислений для извлечения необходимых данных из матриц проверки четности, выбранных пользователем, а также для преобразования элементов в каждой матрице проверки четноти в оптимизированный формат для хранение в ПЗУ декодера.
Как показано в верхней части рисунка 4.1, первый этап нашего программного обеспечения для интерпретации матрицы проверки четности заключается в вычислении параметров декодера на основе характеристик заданного пользователем набора матрицы проверки четности и выбранного коэффициента уменьшения параллелизма Q. В частности, это: факторы параллелизма P и Pc, максимумы различных параметров матрицы проверки четности NB, MB, Z, DC и DV, отношение блоков обработки VN к блокам обработки CN Gmin, параметр гибкости F, и дополнительный параметр гибкости для матрицы проверки четности L.
Вторая задача интерпретации матрицы проверки четности программного обеспечения, изображенного на рисунке 4.1, заключается в извлечении местопо ложений и сдвиговых значений непустых подматриц в каждой матрице проверки четности Hь и их упорядочении в формате, совместимом с ПЗУ. Здесь каждая строка rІ, в каждом Hь должна быть циклически сдвинута вправо на i - 1 места, чтобы гарантировать, что все адреса определяют способ, которым внешние LLR, связанные с каждой подматрицей, хранящейся в памяти декодера переменного узла и памяти декодера проверочного узла. Затем ПЗУ заполняются значениями относительно наличия, местоположения и значения ненулевых записей в сдвинутом Нь.
2) Генерация HDL. Чтобы программно генерировать код System Verilog в пользовательском приложении, полная библиотека генерации System Verilog была написана на С ++. Таким образом, автономный поток разработки может генерировать полное описание System Verilog LDPC-декодера, имеющего предлагаемую архитектуру, с использованием параметров и значений, вычисленных на предыдущем этапе, как показано на рисунке 4.1. В дополнение к автоматическому созданию надежного кода с использованием соответствующих параметров этот подход позволяет не всегда включать определенные элементы, которые могут не потребоваться во всех приложениях.
Эти элементы включают входной сигнал выбора матрицы проверки четности, который не требуется, когда декодер предназначен для поддержки только одной матрицы проверки четности, а также гибких блоков обработки CN, которые не требуются, когда параметр гибкости декодера имеет значение F = 0. Выходные файлы, созданные этой библиотекой, могут быть прочитаны и отредактированы вручную, если это необходимо, перед использованием любым инструментом синтеза, который поддерживает System Verilog HDL. Как показано на рисунке 4.1, синтез этих файлов соответствующим инструментом приведет к измерению аппаратных требований результирующего декодера, в то время как его производительность обработки и эффективность коррекции ошибок могут быть охарактеризованы с помощью моделирования битовых ошибок (BER) на ПЛИС. Эти характеристики могут быть использованы для направления выбора другого значения для коэффициента уменьшения параллелизма Q, если это необходимо, что потребует повторения проектного потока, как показано на рисунке 4.1.
3) Генерация дерева блока обработки узлов. Полное определение внутренней структуры дерева узлов приводит к аппаратным средствам с предпочтительной комбинацией использования ресурсов и рабочей частоты, по сравнению со структурами, определяемыми исключительно за счет инструмента синтеза. Однако чтобы реализовать это в предлагаемом автоматизированном проекте, модель этой древовидной структуры должна быть алгоритмически определена.
Структура дерева с минимальной глубиной может быть сформирована, используя любое положительное целое число у, которое может быть рассчитано как сумма двух целых чисел х} и х2, где х} - наивысшая степень двух меньших у. Затем этот процесс можно применить рекурсивно, используя х\ или х2 как у, генерируя дерево из двух входных функций, имеющих критический путь, содержащий не более [log2 (у)] дополнения. Таким образом, внутренняя структура блока обработки VN может быть программно выражена установкой у= Dv + 1, что дает результат, показанный на рисунке 3.1 для Dv = 12. Таким образом, эта структура может быть использована повторно в блоках обработки CN, где функция min используется вместо суммирования. Однако вместо того, чтобы создать единое дерево для комбинации Dc элементов, вместо Dc деревьев требуются (Dc -1) элементы. В [86] узлы предназначены для повторного использования столько раз, сколько возможно, используя метод, описанный в [86]. Вышеупомянутое HDL приложение использует этот метод для генерации блоков обработки узлов любой степени, не полагаясь на переменные результаты.