АППАРАТНая РЕАЛИЗАЦИя КОДИРОВАНИЯ ИНФОРМАЦИИ систематическими ПОЛЯРНЫМИ КОДАМИ

Полный текст

Введение. В настоящее время помехоустойчивое кодирование является неотъемлемой частью любой современной системы связи, в том числе космической. Применение помехоустойчивого кодирования позволяет снизить уровень ошибок в передаваемых сообщениях и повысить надежность передачи сообщений. Полярные коды, предложенные Эрдалом Ариканом, имеют большое практическое значение, поскольку доказано, что они достигают пропускной способности симметричных каналов без памяти [1]. Кроме того, для полярных кодов характерно отсутствие области насыщения ошибок [2] и низкая сложность реализации [3]. Однако полярные коды имеют два существенных недостатка: во-первых, низкую эффективность для коротких кодов и кодов средней длины по сравнению с LDPC-кодами аналогичной длины, а во-вторых, алгоритм последовательного исключения (successive cancellation, SC), предложенный Ариканом для декодирования полярных кодов в [1], является последовательным по своей природе, что влечет за собой низкую пропускную способность. В настоящее время существует ряд методов, решающих эти проблемы. Дальнейшим развитием идеи полярных кодов являются систематические полярные коды [4], позволяющие значительно снизить уровень битовых ошибок в передаваемых сообщениях. Для повышения эффективности полярных кодов был предложен ряд новых алгоритмов декодирования, развивающих идеи SC-декодирования [5-7]. Также был предложен ряд решений, повышающих пропускную способность алгоритмов декодирования [8; 9]. В статье представлен обзор существующих подходов к аппаратной реализации кодирования полярных кодов. Выделена и подробно рассмотрена операция прекодирования - предварительного преобразования информационного сообщения длины K в сообщение длины N, предложен вариант аппаратной реализации. Разработано устройство систематического кодирования полярными кодами, включающее в себя блок, реализующий операцию прекодирования. Кодирование полярными кодами. Полярные коды относятся к классу двоичных линейных блоковых кодов. В основе процедуры кодирования полярными кодами лежит операция поляризации канала, которая описывается линейным преобразованием, задаваемым матрицей , где F - 2 × 2 - ядро поляризации, ; - n-кратное кронекеровское произведение матрицы с собой; n = log2N, где N - длина кодового слова конструируемого кода. Полярный код С задается набором параметров (N, K, Ac), где N - длина кодового слова; K - размер информационной части; Ac - множество «замороженных» символов, значение которых равно нулю, |Ac| =N - K, . Методы построения полярных кодов подробно рассмотрены в [1; 10]. Несистематическое кодирование полярными кодами описывается выражением , (1) где - кодовое слово; - вектор, включающий информационные символы (, 1 ≤ i ≤ N) и «замороженные» позиции (, 1 ≤ i ≤ N); GN - порождающая матрица полярного кода, задаваемая матрицей . Если порождающая матрица задается выражением , (2) где BN - матрица перестановки, то код называется полярным кодом с битовой перестановкой (bit-reversed) [1]. Если порождающая матрица задается выражением , (3) то код называется полярным кодом без битовых перестановок (non-reversed) [4]. Схемы bit-reversed и non-reversed (8, 5, {1, 3, 5})-полярных кодов представлены на рис. 1. Систематическое кодирование. Систематическое кодирование позволяет не изменять значения информационных битов. Кроме того, оно позволяет значительно снизить уровень битовых ошибок [4]. Процедура кодирования описывается выражением , (4) где GN может соответствовать как выражению (2), так и выражению (3). В векторе значения равны значениям информационных битов, а значения неизвестны. В векторе значения равны нулю, неизвестны. После решения уравнения (4) вектор является кодовым словом систематического полярного кода. Алгоритмы программной реализации систематического кодирования полярными кодами подробно рассмотрены в [11]. Рис. 2 иллюстрирует операцию систематического кодирования non-reversed (8, 5, {1, 3, 5})-кодом. Для bit-reversed полярного кодирования операция систематического кодирования аналогична, за исключением соединения элементов «исключающее ИЛИ», которое соответствует рис. 1. В работах [12; 13] рассматривается метод реализации систематического кодирования полярными кодами через двукратную операцию несистематического кодирования. Для этого необходимо: 1) преобразовать информационное сообщение в сообщение в соответствии с Ac; 2) осуществить процедуру несистематического кодирования над вектором , получить вектор ; 3) обнулить символы ; 4) осуществить процедуру несистематического кодирования над измененным вектором , получить вектор . На рис. 3. представлена схема систематического кодирования на основе несистематического non-reversed кодирования. а б Рис. 1. Схемы полярного (8, 5, {1, 3, 5})-кода: bit-reversed (а); non-reversed (б) Рис. 2. Схема систематического non-reversed полярного кодирования (8, 5, {1, 3, 5})-кодом Рис. 3. Схема систематического кодирования на основе несистематического non-reversed кодирования (8, 5, {1, 3, 5})-полярным кодом Прекодирование информации. Термином «прекодирование» обозначим операцию преобразования информационного сообщения в сообщение в соответствии с множеством Ac: Прекодирование для (8, 5, {1, 3, 5})-кода будет выглядеть так: Введем понятие маски полярного кода. Маска полярного кода - это вектор m длины N такой, что mi = 0 для и mi = 1 для . Для (8, 5, {1, 3, 5})-кода маска полярного кода имеет вид m = {0, 1, 0, 1, 0, 1, 1, 1}. Операция прекодирования может быть реализована с использованием регистров сдвига вправо (рис. 4, 5). Прекодирование (8, 5, {1, 3, 5})-полярного кода потребует 5-разрядный сдвиговый регистр D для вектора d, 8-разрядный сдвиговый регистр M для вектора m и 8-разрядный сдвиговый регистр U для вектора u. Сдвиг в регистре M осуществляется на каждом цикле работы, на выход поступает значение младшего бита M1. Сдвиг в регистре D осуществляется при условии M1 = 1. Входной сигнал регистра U равен M1^D1. На рис. 4, а описывается состояние регистров прекодера (8, 5, {1, 3, 5})-полярного кода. В первый цикл работы осуществляется загрузка вектора m в регистр M и вектора d в регистр D. Непосредственно операция прекодирования осуществляется за следующие 8 циклов. Таким образом, прекодирование вектора u для (8, 5, {1, 3, 5})-кода осуществляется за N+1 циклов. Схема прекодера (8, 5, {1, 3, 5})-полярного кода приведена на рис. 5, а. Перейдем к обобщенной схеме прекодера с разрядностью P регистров сдвига D, M и U, кратной N и K. Рассмотрим подробно диаграмму состояний такого прекодера с P = 4, представленную на рис. 4, б: Цикл 1: загрузка в рег. D; загрузка в рег. M; простой в рег. U. Цикл 2: сдвиг в рег. D; сдвиг в рег. M; U4 = d1. Цикл 3: сдвиг в рег. D; сдвиг в рег. M; Цикл 4: простой в рег. D; сдвиг в рег. M; Цикл 5: сдвиг в рег. D; сдвиг в рег. M; - прекодирование завершено. Цикл 6: простой в рег. D; простой в рег. M; простой в рег. U. Цикл 7: простой в рег. D; загрузка в рег. M; простой в рег. U. Цикл 8: простой в рег. D; сдвиг в рег. M; Цикл 9: простой в рег. D; сдвиг в рег. M; Цикл 10: сдвиг в рег. D; сдвиг в рег. M; Цикл 11: загрузка в рег. D; простой в рег. M; простой в рег. U. Цикл 12: простой в рег. D; сдвиг в рег. M; - прекодирование завершено. Цикл 13: простой в рег. D; загрузка в рег. M; простой в рег. U. Цикл 14: сдвиг в рег. D; сдвиг в рег. M; Прекодирование длилось в течение циклов 1-5, начиная с загрузки и , затем в течение цикла 6 происходит простой прекодера. Прекодирование длилось в течение циклов 7-12, начиная с загрузки . Разница в один цикл связана с тем, что при прекодировании загрузка и происходит в циклах 7 и 11 соответственно. Таким образом, простои, аналогичные простою в цикле 6, вводятся для того, чтобы прекодирование P бит всегда осуществлялось за P+2 цикла. Схема обобщенного прекодера с P = 4 представлена на рис. 5, б. Для реализации необходимо добавить сигналы разрешения сдвига Shift_en для регистров M и U. Shift_en = 0 в том случае, если регистр маски M уже не содержит бит маски, но еще не прошло P+2 цикла с прошлой операции прекодирования. Методы аппаратной реализации несистематического кодирования. Схемы несистематических полярных кодов, рассмотренные выше, могут быть реализованы в виде комбинационной схемы - параллельного кодера. Такое устройство имеет N входов, включает в себя элементов «исключающее ИЛИ» и осуществляет кодирование за n этапов. Очевидным недостатком такого решения является его плохая масштабируемость, поскольку при параллельной реализации разрядность входа и выхода такой схемы равна длине кодового слова N. Для минимизации разрядности входа и выхода схемы кодирования необходимо применение методов конвейеризации вычислений [14]. Первым из рассматриваемых вариантов применения методов конвейеризации является конвейерная схема несистематического bit-reversed кодера [15; 16] с разрядностью входного и выходного сигнала P и длиной кодового слова N. На рис. 6. Представлена схема с P = 4 и N = 16. Другой вариант - конвейерный несистематический non-reversed кодер с P = 4 и N = 16, представлен на рис. 7 [13]. В таблице приведены сравнительные характеристики параллельного кодера и рассматриваемых схем. Как видно из таблицы, кодер 1 требует меньшего количества элементов «исключающее ИЛИ», чем кодер 2. Недостаток кодера 1 проявляется при реализации систематического кодирования согласно схеме на рис. 4. В этом случае требуется хранить маску полярного кода в non-reversed форме для осуществления прекодирования информации и в bit-reversed форме для наложения маски в ходе систематического кодирования, что влечет за собой дополнительные расходы ресурсов памяти. б а Рис. 4. Состояние регистров прекодера (8, 5, {1, 3, 5})-полярного кода (а); состояние регистров обобщенного прекодера с P = 4 (б) а б Рис. 5. Схема прекодера (8, 5, {1, 3, 5})-полярного кода (а); обобщенная схема прекодера (б) Рис. 6. Конвейерный несистематический bit-reversed (16, K)-кодер с P = 4 (кодер 1) Рис. 7. Конвейерный несистематический non-reversed (16, K)-кодер с P = 4 (кодер 2) Сравнительные характеристики рассматриваемых схем кодирования Характеристики Параллельная схема Кодер 1 [15; 16] Кодер 2 [13] Разрядность N P P «Искл. ИЛИ» Регистры - Мультиплексоры - Задержка кодирования 0 Кодер систематического полярного кода. На рис. 8 представлена структурная схема разработанного устройства систематического (32, 16)-полярного кода с разрядностью P = 8. Систематическое кодирование реализуется в соответствии со схемой на рис. 3. Временная диаграмма конвейера систематического (32, 16)-кодера представлена на рис. 9. Блок «Прекодер» реализует операцию прекодирования и является обобщенным прекодером с P = 8. Он преобразует информационное сообщение I в вектор U в соответствии с маской полярного кода M, результат записывается в регистр 1. Блоки «НСК 1» и «НСК 2» - конвейерные несистематические non-reversed (32, K)-кодеры с P = 8. Блок «НСК 1» кодирует вектор U в X’. Наложение маски M на вектор X’ осуществляется с помощью двухвходового элемента «И», результат записывается в регистр 2. Затем блок «НСК 2» кодирует преобразованный вектор X’ в вектор X, который и является кодовым словом. Кодирование сообщения (N, K)-кодером разрядности P осуществляется за стадий, длительность каждой стадии составляет цикла, общее время кодирования составляет циклов. Отношение длительности цикла предлагаемого систематического кодера TСК к длительности цикла блока «Прекодер» ТПр описывается выражением TСК = (P + 2)ТПр. Разработанный систематический кодер был смоделирован в пакете Altera Quartus II 13.0 с использованием системы ModelSim 10.1. На рис. 10 приведены результаты симуляции в системе ModelSim 10.1. Моделировалось систематическое кодирование информационного сообщения d = 16’h{2F, 59} (32, 16)-полярным кодом с маской m = 32’h{88, E8, E8, EE}. Результат кодирования равен x = 32’h{AC, AC, 53, 5C}. Результат моделирования совпадает с результатом моделирования систематического полярного (32, 16)-кода в пакете MATLAB R2016b, построенного с использованием библиотеки [17]. Заключение. В работе представлен обзор метода помехоустойчивого кодирования, получившего название полярного кода. Рассмотрены методы кодирования полярными кодами и варианты их аппаратной реализации. Выделена операция прекодирования, предложен метод ее аппаратной реализации. Разработано устройство систематического кодирования полярными (32, K)-кодами, реализующее также и операцию прекодирования, проведено его моделирование. Разработанное устройство может быть масштабировано для кодирования информации полярными кодами с практически значимыми значениями длины кодового слова N. Рис. 8. Структурная схема систематического (32, 16)-кодера Рис. 9. Временная диаграмма конвейера систематического (32, 16)-кодера Рис. 10. Результаты симуляции в системе ModelSim 10.1

Об авторах

Г. С. Тимофеев

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева

Email: t1m0feev.grigorij@gmail.com
Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31

Список литературы

Дополнительные файлы