Разработка кодека сверточного кода с алгоритмом порогового декодирования
Обновлено: 07.07.2024
Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Е. Г. МакейЧик, А. И. КоролёВ, В. К. Конопелько
Рассматривается эффективность порогового декодирования недвоичных самоортогональных сверточных кодов в канале связи с аддитивным белым гауссовским шумом при коррекции t t 1 символьных ошибок. Символы или элементы кодовых последовательностеи ̆ (КП) используемого самоотрогонального сверточного кода со скоростью передачи кода R k0 n0 1 2 являются элементами конечного поля GF ai , i 2 . Количество ошибочных кодовых символов и их позиций в принятой КП на длине кодового ограничения na m 1 n0 двоичных символов определяется декодером на основе структуры сформированной синдромной последовательности (СП) SxS0, S1,, SN, зависящей от структуры ошибок в канале связи и структуры порождающих полиномов: m – максимальная степень порождающих полиномов. Установлено, что при сохранении достоинств порогового алгоритма декодирования обеспечивается увеличение в i i 2 раз кратности корректируемых ошибок двоичными самоортогональными кодами при равной скорости передачи кодов.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Е. Г. МакейЧик, А. И. КоролёВ, В. К. Конопелько
Методы неравной защиты информационных символов на основе сверточных кодов Коррекция зависимых ошибок турбокодеком на основе вложенных равномерных сверточных кодов Коррекция зависимых ошибок на основе равномерных сверточных кодов Пороговое декодирование сверточных кодов в каналах связи с фазовой неопределенностью i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.Threshold decoding of hospitals self-original conventional codes
The efficiency of threshold decoding of non-binary self-orthogonal convolutional codes in the communication channel with additive white Gaussian noise with the correction of tt1symbolic errors is considered. The characters or elements of the code sequence (CS) used by the self-triggered convolutional codewiththecodetransmissionrateequaledRk0 n012aretheelementsofthefinalfieldGFai,i2. The number of erroneous code symbols and their positions in the received CS on the length of the code constraint equaled na m 1 n0 binary symbols is determined by the decoder based on the structure ofthegenerated syndrome sequence (SS) SxS0, S1,, SN, depending on the structure of errors inthecommunication channel and the structure of the generating polynomials: m is maximum degree of the generating polynomials. It has been established that while preserving the merits of the threshold decoding algorithm, an increase in i i 2 times the multiplicity of corrected errors is ensured by binary self-orthogonal codes with an equal transfer rate of codes.
Текст научной работы на тему «Пороговое декодирование недвоичных самоортогональных сверточных кодов»
2018, № 8 (118) 2018, No. 8 (118)
ПОРОГОВОЕ ДЕКОДИРОВАНИЕ НЕДВОИЧНЫХ САМООРТОГОНАЛЬНЫХ СВЕРТОЧНЫХ КОДОВ
Е.Г. МАКЕЙЧИК, А.И. КОРОЛЁВ, В.К. КОНОПЕЛЬКО
Белорусский государственный университет информатики и радиоэлектроники, Республика Беларусь
Поступила в редакцию 10 октября 2018
Ключевые слова: самоортогональный сверточный код, кодовые последовательности, скорость кода, пороговое декодирование, порождающий полином.
of the generated syndrome sequence (SS) S(x) = , depending on the structure of errors
in the communication channel and the structure of the generating polynomials: m is maximum degree of the generating polynomials. It has been established that while preserving the merits of the threshold decoding algorithm, an increase in i (i > 2) times the multiplicity of corrected errors is ensured by binary self-orthogonal codes with an equal transfer rate of codes.
Keywords: self-orthogonal convolutional code, code sequences, code speed, threshold decoding, generator polynomial.
Doklady BGUIR. 2018, Vol. 118, ]Чо. 8, pp. 101-107
Threshold decoding of hospitals self-original conventional codes
E.G. Makeichik, A.I. Korolev, V.K. Kanapelka
Повышение достоверности передачи информации является актуальной задачей современных цифровых систем связи. Эффективным способом решения этой задачи является применение помехоустойчивого кодирования. Среди используемых помехоустойчивых кодов для решения этой задачи широкое применение получили самоортогональные сверточные коды (ССК) с алгоритмом порогового декодирования. Высокие корректирующие свойства обеспечивают недвоичные ССК. Разрабатывается реализация канального кодека на основе недвоичного ССК с алгоритмом порогового декодирования, обеспечивающего минимальную сложность реализации кодека и задержку информационных символов при декодировании.
Общий принцип порогового декодирования недвоичных самоортогональных сверточных кодов
Известно 1, что ССК с пороговым алгоритмом декодирования - это такой рекурентный код, который формирует полубесконечные КП, структура которых зависит от структуры передаваемой информации, количества и структуры порождающих полиномов
Рис. 1. Проверочная матрица ССК с алгоритмом порогового декодирования
Блоки В0 представляют собой полубесконечные проверочные подматрицы, каждая из которых имеет «Ь» столбцов, неопределенное количество строк и определенное количество ненулевых позиций (ненулевых символов), а все остальные позиции проверочной матрицы H -целое число, при котором произведение N ■ Ь проверочной подматрицы формирует в целом проверочную матрицу H. Параметр «Ь» определяет длину мини-блока КП. В целом количество N строк проверочной подматрицы В0 достаточно для формирования проверочной матрицы H.
Формирование полубесконечных КП ССК осуществляется по следующему правилу 1:
где I(]) (О) - полубесконечная последовательность передаваемых информационных символов; О^]) (О) - порождающий полином.
Сформированная полубесконечная КП, принятая без ошибок на приемной стороне, должна удовлетворять следующему уравнению 1:
Допустим, что I представляет 1-й ввод или символ КП, а первые «т» строк проверочной матриц H можно представить как «т» уравнений с «Ь» неизвестными 11.1Ь.
Контрольные (проверочные) «т» символов определяют избыточность и, соответственно, скорость передачи кода, а именно [4, 5]
R = ( Ь — т )/Ь = к0/ п
где Ь = к0 - мини-блок информационных символов; п0 - мини-блок кодовых символов,
симв., где в - максимальная степень порождающих полиномов сверточного кода.
Кодовые символы вышеопределенного ССК являются элементами конечного поля
G(g1), где g = 0;1 - размер алфавита, I = 2;3;4;. - размерность символа, т. е. число
элементов (битов) алфавита в кодовом символе. Далее, при рассмотрении порогового алгоритма декодирования недвоичного ССК принимаем т = 1.
Учитывая, что проверочная подматрица В0 двоичного ССК корректирует
t(г > 2) -кратные ошибки со скоростью кода R = (Ь — 1)/Ь , то проверочная матрица ССК корректирует t = 1 (одиночные символьные) ошибки со скоростью кода
где к - произвольно выбранный элемент, строящийся по следующему алгоритму 3:
Шаг 1. Заменим 7-й ненулевой элемент ]-й колонки подматрицы В0 на ряд векторов
где а - простой элемент ш g
Шаг 2. Заменим все нулевые вводы подматрицы на нулевые ряды векторов размерности к (параметр к - произвольно выбранный для получения ССК со скоростью кода
Шаг 3. Оставим последнюю колонку (колонка проверки на четность) подматрицы В0 неизменной.
1 1 1 1 а 0 0 0 0 0 0 0 1 а2 0 000 1 а3 0
111 1 а 0 000 000 1 а2 0 000
111 1 а 0 000 000 1 а2 0
111 1 а 0 000 000
Рис. 3. Обобщенная функциональная схема канального кодера недвоичного самоортогонального сверточного кода
Связи регистра сдвига канального кодера с многовходовым сумматором по mod p определяются проверочной матрицей (рис. 2) - так называемыми позициями
информационных символов, соответствующих первым двум позициям каждой из семи колонок нижней строки матрицы. Каждое из этих значений соответствует одному из символьных регистров кодера. Выходы второго, девятого и тринадцатого трехбитовых регистров сдвига подключаются к сумматору по modp через умножение на элементы а1, а2 и а3 соответственно. Нулевые двоичные символы «0» в первых двух позициях как четвертой, так и пятой колонок матрицы указывают, что выходы 4, 5, 6 и 7 трехбитовых регистров не подключаются к сумматору по mod p .
Формирование кодовых символов выполняется следующим образом. Источник информации выдает трехбитовые информационные символы в канал связи и на RG кодера. Второй информационный символ каждой пары символов также поступает на сумматор по mod p вместе с выходными символами первого, третьего девятого и тринадцатого регистров. Кроме того, на сумматор по mod p поступают символы с выходов трехбитовых
регистров - второго, восьмого и двенадцатого, умноженных на коэффициенты а1 , а2 и а3 соответственно. Схемы умножения на константы являются простыми умножителями, используемыми для умножения символов на постоянную величину. Сформированный проверочный (контрольный) символ с выхода сумматора по mod p поступает на вход проверочного трехбитового регистра.
После каждой пары информационных символов, переданных в канал связи, источник информации отключается от входа кодера, и в канал связи выдается сформированный проверочный символ, после чего вновь подключается ко входу кодера источник информации, который снова выдает два трехбитовых информационных символа, и процесс кодирования информации, описанный выше, повторяется. Таким образом, проверочный трехбитовый символ формируется для каждой пары трехбитовых информационных символов. Сформированная группа из трех трехбитовых символов носит название кодового блока и определяет скорость кода R = 2/3 . Обобщенная функциональная схема, иллюстрирующая принцип построения недвоичного канального декодера ССК, приведена на рис. 4: [Щ -трехбитовый регистр сдвига; © - сумматор по mod 2; О - схема умножения на константу; ФСУд - формирователь символов управления декодера.
Рис. 4. Обобщенная функциональная схема канального декодера недвоичного самоортогонального сверточного кода
на вход формирователя проверочных символов декодера или кодера ФПСд(к), имеющего структуру построения и принцип работы аналогично канальному кодеру. Принципиальное отличие ФПСд от канального кодера состоит только в том, что RG ФПСд имеет на один символьный трехбитовый регистр больше, чем канальный кодер.
Сформированные проверочные символы Рсф (D) поступают на один из входов формирователя синдромных символов или синдрома (ФСС), выполняемого в виде сумматора по mod p, на второй вход которого поступают принятые проверочные символы Рсф (D). Символы синдрома, используемые для определения достоверности принятых информационных символов, определяются, как указывалось выше, матрицей (рис. 2): означенные элементы записываются на те места первого столбца матрицы, которые являются ненулевыми. То есть, первый, второй, пятый и седьмой символы синдрома, которые хранятся в трехбитовых регистрах анализатора синдромной последовательности (АСП), записываются соответственно в первую, вторую, пятую и седьмую ненулевые ячейки первого столбца .
После поступления каждого нового синдромного символа в RG АСП, содержимое первого, третьего и шестого регистров переписывается в трехбитовые регистры деления. Далее содержимое первого, третьего, шестого и седьмого регистров переносится в главную логическую схему: если три из четырех символов синдрома S0, S1; S2, S3 - ненулевые, то главная логическая схема выдает сигнал (импульс) на вход схемы «И», что указывает
на то, что один из информационных символов является ошибочным. Пусть ошибочным будет i . В этом случае, исследуя матрицу и, в частности, крайний левый столбец, который переписывается в самую правую позицию RG АСП, можно заметить, что три из четырех символов S0, Sj, S2, S3 будут ненулевыми (если ошибочным был только один информационный символ, то все четыре символа синдрома S0, Sj, S2, S3 будут ненулевыми). Тем не менее может быть ошибочным и другой информационный символ на длине кодового ограничения. Однако эта ошибка на момент декодирования первого ошибочного информационного двухбитового символа изменит полярность (уровень) только одного синдромного символа из четырех и, следовательно, выполнится коррекция ошибочного символа.
Далее предположим, что ошибочным является символ i2, записанный в третий справа трехбитовый символьный регистр. В этом случае снова или, по крайней мере, два из трех компонентов синдрома Sj, S2, S3 будут отличаться от S0 умножением на а . Если Sj - один из таких компонентов, то он будет умножен на а (кратен а) и будет отличаться от S0. Аналогично проводятся операции с компонентами S2, S3 — умножение соответственно на а
Так как S0 = ej © e2, Sj = ej © ае2, S2 = ej © а2е2 и S3 = ej © а3е2, то суммируя S0, Sj, S3, получим
Таким образом, ошибочный элемент e1 может быть получен путем суммирования по mod 2 S0, S1, S3. Когда символы i1 и i2 ошибочны, по цепи Е поступает импульс e1, и далее выполняется операция
Эта операция выполняется сумматорами по mod 2 (К, М, Н) и соответствующими
делителями (а-1) и (а-2). Если же условия выполняются, то на выходе трехвходовой
схемы «И» будет высокий уровень, который через схему «И» во время получения t1, поступившего от главной логической схемы, далее поступает через пятивходовую схему «ИЛИ» и двухвходовую схему «И» на выходной сумматор по mod 2 .
Данные компоненты синдрома, поступившие на входы сумматора по mod 2, формируют на его выходе импульс с высоким уровнем, который при поступлении временного интервала t3 от главной логической схемы поступит через пятивходовую схему «ИЛИ» и двухвходовую схему «И» на выходной сумматор по mod 2 e2 © i2. В результате этого будет выполнена коррекция ошибочного символа i2. Исправленные версии двух трехбитовых информационных символов i1 и i2 поступят к получателю информации.
Предложенный метод построения канального кодека на основе недвоичного ССК с алгоритмом порогового декодирования обеспечивает двукратное увеличение корректирующей способности по сравнению с двоичным ССК при равных скорости передачи кода и количестве ортогональных проверок. Данный метод построения канального кодека может быть легко применим для недвоичных ССК с другими параметрами.
1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.2. Кларк Дж. мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1982. 392 с.
3. Морелос-Сарога Р. Искусство помехоустойчивого кодирования: методы, алгоритмы применения. М.: Техносфера. 2005. 320 с.
4. Теория прикладного кодирования: в 2 т. / В.К. Конопелько [и др.]. Минск: БГУИР, 2004. 688 с.
5. Королев А.И., Ахмед Саид Аль-Алем, Конопелько В.К. Помехоустойчивое кодирование информации. Минск: Бестпринт, 2013. 276 с.
1. Bleihyt R. Teorua i praktika kodov, kontroliryiyih oshibki. M.: Mir, 1986. 576 s. (in Russ.)
2. Klark Dj. ml., Kein Dj. Kodirovanie s ispravleniem oshibok v sistemah tsifrovoi sviazi. M.: Radio l sviaz, 1982. 392 s. (in Russ.)
3. Morelos-Saroga R. Iskуsstvo pomehoystoichivogo kodirovaniia: metody, algoritmy primeneniia. M.: Tehnosfera. 2005. 320 s. (in Russ.)
5. Korolev A.I., Ahmed Said Al-Alem, Konopelko V.K. Pomehoystoichivoe kodirovanie informatsii. Minsk: Bestprint, 2013. 276 s. (in Russ.)
Сведения об авторах
Макейчик Е.Г., старший преподаватель кафедры инфокоммуникационных технологий Белорусского государственного университета информатики и радиоэлектроники.
Королёв А.И., к.т.н., доцент, доцент кафедры инфокоммуникационных технологий
Белорусского государственного университета информатики и радиоэлектроники.
Конопелько В.К., д.т.н., профессор, профессор кафедры инфокоммуникационных технологий Белорусского государственного университета информатики и радиоэлектроники.
В общем виде кодирование информации СК может быть представлено следующим образом:
j=1…k0, i=j+1,
где I(x) - последовательность передаваемых информационных символов;
x - оператор задержки;
g(x) - порождающий или образующий полином (многочлен);
Способ формирования кодовых символов, выполняемых согласно (1.1), соответствует форме записи свёртки двух функций, что и послужило названию данных кодов. Свёрточный код - это рекуррентный код с периодической полубесконечной структурой символов кодовой последовательности. Обобщённая структурная схема кодера СК имеет следующий вид, представленный на рисунке 1.1:
Рисунок 1.1 - Обобщённая структурная схема кодера
ССК - это коды, у которых декодируемый информационный символ входит одновременно во всех проверочных уровнях, а все остальные символы, участвующие в декодировании в данный момент времени, входят не более, чем в одно проверочное уравнение, т.е. СКК формирует, так называемую, систему раздельных проверок.
К основным характеристикам ССК относятся:
- 1. Длина миниблока информационных символов (количество информационных подпотоков, на которое распределяется входной информационный поток (I(D))) - k0;
- 2. Длина миниблока кодовых символов - n0;
- 3. Скорость передачи кода, определяемая соотношением:
Она характеризует избыточность, вводимую при кодировании. Большие скорости кода позволяют увеличить пропускную способность канала связи, зато снижение скорости уменьшает количество ошибок на выходе приёмника.
4. Относительная избыточность кода:
- 5. Количество ортогональных проверочных уравнений кода - J;
- 6. Кратность или колличество исправляемых ошибок:
7. Минимальное кодовое расстояние кода:
- 8. Максимальная степень порождающего полинома g(x) - m;
- 9. Память кода, называемая также входной длиной кодового ограничения или информационной длиной кодового слова, соответствующая кодированию информационных блоков из k0 символов в течение (m+1) тактов:
Определяется максимальной степенью порождающего многочлена.
10. Кратность обнаруживаемых ошибок:
11. Эффективная длина кодового ограничения:
12. Вероятность безошибочного декодирования ССК, определяемая по формуле:
где d0 - минимальное кодовое расстояние ССК;
рk - исходная вероятность ошибки в канале связи;
- - вероятность безошибочного приема в канале связи.
- 13. Достоверность передаваемой информации при использовании ССК точнее оценивается вероятностью первой ошибки декодирования, определяемой по формуле :
где t - кратность исправляемых ошибок;
- эффективная длина кодового ограничения;
рk - исходная вероятность ошибки на выходе модема или канала связи;
- вероятность безошибочного приема информации.
Для порогового декодирования вероятность ошибочного декодирования в первом символе P1e является нижней оценкой средней вероятности ошибки Pср.
ССК могут задаваться с помощью образующего многочлена, порождающей и проверочной матрицы, и с помощью кодового дерева.
ССК задаются следующей порождающей матрицей G:
Для ССК с алгоритмом порогового декодирования проверочная матрица H задается следующим образом:
Из данной проверочной матрицы следует, что для ССК с
проверочная матрица Н содержит (n0-k0) строк и k0 столбцов проверочных треугольников. Для ССК с
n0= 2;3;…,
проверочная матрица Н содержит k0=1, т.е. один столбец и (n0-1) строк проверочных треугольников.
Каждый из проверочных треугольников Н i, k0+i, i=1,2, …; k0=1,2, …, проверочной матрицы Н в общем случае имеет вид:
где q - коэффициенты, равные либо 1, либо 0; j, i - номера соответственно строки и столбца матрицы Н, которыми определяется проверочный треугольник; 0, …m - порядковые номера степеней, в которые возводятся соответствующие коэффициенты порождающего полинома.
Основную информацию о самоортогональных сверточных кодах ССК несут коэффициенты левого столбца и нижней строки проверочного треугольника.
Так как проверочный треугольник позволяет определить практически все параметры ССК, то разработано много способов построения. Однако на практике наибольшее применение получили два способа их построения, а именно с помощью нахождения разностных треугольников и совершенных разностных множеств. Сущность их состоит в следующем.
Разностный треугольник представляет собой совокупность целых, действительных и неповторяющихся чисел, записанных в форме треугольника. Для ССК с
R = k0/n0
количество разностных треугольников равно числу k0. Для всех разностных треугольников общим числом является “0”, который не указывается в совокупности чисел, однако учитывается при выборе степеней ненулевых членов порождающих полиномов. Очевидно, что число “0” определяет нулевую степень первых ненулевых членов порождающих полиномов. Степени ненулевых членов порождающих полиномов по заданным или построенным разностным треугольникам можно найти путем выбора чисел: левого крайнего столбца разностного треугольника, считывая их сверху вниз и дополняя числом “0”, или верхней строки разностного треугольника в такой последовательности: первое число - показатель степени второго ненулевого члена порождающего полинома; суммирование первого и второго чисел первой строки разностного треугольника определяет показатель степени третьего ненулевого члена порождающего полинома и т.д.
Разностный треугольник ССК может быть построен, если задан проверочный треугольник, и наоборот. Например, используя проверочный треугольник (1.15) можно построить разностный треугольник, следующим образом:
Числа крайнего левого столбца разностного треугольника определяются как результат операции вычитания порядковых номеров строк проверочного треугольника, которые начинаются с "1". Для первого столбца получаем следующие числа:
- 3-1=2
- (3 - номер позиции третьей строки; 1 - номер позиции первой строки);
- 6-1=5
Для получения чисел второго столбца за вычитаемое берем номер позиции третьей строки:
Для получения чисел третьего столбца за вычитаемое берем номер позиции шестой строки:
В итоге получаем следующий разностный треугольник:
При выборе чисел для построения разностных треугольников необходимо выбирать числа с наименьшим их значением по номиналу, т.к. максимальное значение числа в построенных разностных треугольниках определяет максимальную степень m порождающих полиномов ССК.
Пороговое декодирование ССК обеспечивается алгоритмом формирования системы J (J2) проверочных уравнений (проверок), а именно: система проверок формируется таким образом, что декодируемый информационный символ входит во все проверки, а все остальные символы входят только в одну проверку (проверочное уравнение). Для этого следует использовать транспонированную проверочную матрицу , имеющую вид:
где Н m - проверочный треугольник; Im - единичная матрица.
Например, для ССК, задаваемого полиномом
g(x)=1+x 2 +x 5 +x 6 , Н T7
выглядит следующим образом:
Из матрицы (1.17) система J ортогональных проверок имеет вид:
S5=E i0+ E i3 + E i5 +E P5,
Поскольку столбцы матрицы (1.17), соответствующие ненулевым двоичным символам последней строки, не имеют ни одной общей строки (кроме последней строки), в которой имели бы общий ненулевой символ, то эти столбцы и система проверок (1.18) ортогональны относительно декодируемого информационного символа. Следовательно, ненулевые двоичные символы последней строки матрицы (1.17) соответствуют символам, участвующим в вычислении синдрома, и поэтому в качестве системы J проверок (1.18) можно использовать символы синдрома, а не линейные комбинации проверок. Это упрощает реализацию алгоритма порогового декодирования ССК.
Отметим, что количество ортогональных проверок J равно числу строк или столбцов, которые начинаются с ненулевых двоичных символов, а размерность проверок определяется количеством ненулевых символов, входящих в строку.
При пороговом декодировании свёрточных кодов вычисляются синдромы (признаки места ошибочных символов), затем эти синдромы или последовательности, полученные посредством линейного преобразования синдромов, подаются на вход порогового элемента. Число пороговых элементов (ПЭ) равно к0, т.е. количеству одновременно декодируемых информационных символов. Число входов каждого ПЭ равно числу ортогональных проверок J. Минимальное число входных символов ПЭ, отличных от нуля и необходимых для принятия решения ПЭ о значении декодируемого символа, называется порогом.
Декодер ССК должен реализовывать следующие операции:
распределять символы принятой кодовой последовательности Т`(х) на n0 потоков, что реализуется демультиплексором;
формировать последовательность проверочных символов из принятых информационных символов Iпр(x) (устройство, аналогичное кодеру);
формировать последовательность синдромных символов
символов синдрома или проверку Jk0 ортогональных проверочных уравнений на четность;
осуществлять коррекцию информационных и синдромных символов.
При пороговом декодировании с использованием обратной связи одновременно с декодированием информационных символов происходит коррекция синдромных символов, использованных при формировании сигнала коррекции. Это выполняется с целью устранения влияния ненулевых символов S(x) на правильное принятие решения при декодировании последующих информационных символов.
1. Функциональная электрическая схема ФПСк (ФПСд), представленная на рис.5, выполняется в виде схем умножения полиномов (многочленов) и реализуется со встроенным сумматором по модулю два и сдвиговым регистром. Такой принцип построения ФПСк целесообразнее использовать в нашем случае, т.к. k0>2 (высокоскоростные ССК).
Т.к. максимальная степень порождающих полиномов равна 47, то сдвиговый регистр содержит m=47 ячеек памяти. Нумерация ячеек ведётся справа налево. Места включения сумматоров по модулю два определяются ненулевыми членами порождающих полиномов; выходной сумматор по модулю два является многовходовым.
2. Важнейшим функциональным боком декодера ССК с алгоритмом ПД является АСП (рис.6), который представляет собой последовательный регистр, содержащий m=47 ячеек памяти, с нумерацией ячеек памяти справа налево, и некоторую совокупность встроенных сумматоров по модулю два. В состав АСП входят k0=7 ПЭ, имеющие по J=4 входа. Места включения сумматоров по модулю два в регистре и подключение входов ПЭ определяются ненулевыми членами порождающих полиномов.
Пороговое декодирование ССК будем выполнять с использованием обратной связи в АСП. Ошибки, исправляемые в очередном блоке, могут влиять на символы синдромов, соответствующих последующим блокам, поскольку свёрточные коды непрерывны. И, для того чтобы декодер смог полностью реализовать свои корректирующие возможности, следует исключить влияние этих ошибок. Вот для чего вводится обратная связь. В этом случае одновременно с коррекцией информационных символов будет производиться коррекция синдромных символов, записанных в регистр АСП и принимавших участие в определении достоверности декодируемых информационных символов.
Составим проверочный треугольник для одного из полиномов, по которому определим ортогональные проверочные уравнения:
g6(x)=1+x 1 +x 8 +x 16
Как было ране рассмотрено получение системы ортогональных проверок из матрицы (17), получим свою систему проверочных уравнениё для данной матрицы:
Все проверочные уравнения получаются по синдромным последовательностям, которые формирует ФСП.
Пороговый элемент конструктивно будет представлять собой мажоритарный элемент, для разработки схемы которого воспользуемся следующей таблицей истинности:
Таблица 3 – Таблица истинности
| x1j | x2j | x3j | x4j | yj |
Построим по полученной функции ПЭ (рис. 7).
Рис.7 – Функциональная электрическая схема ПЭ
 |
Рис.5 – Функциональная электрическая схема ФПСк (ФПСд)
Рис.6 – Функциональная электрическая схема ФСП и АСП
1. КО (рис.8) выполняется в виде четырёх регистров сдвига (т.к. k0=7), каждый из которых содержит по 47 ячеек памяти. На выходе каждого регистра включается сумматор по модулю два, на второй вход которого поступает сигнал коррекции с выхода ПЭ АСП декодера.
Рис.8 – Функциональная электрическая схема КО
Для описания принципа работы КРИ будем использовать временные диаграммы построенные для контрольных точек, отмеченных цифрами в кружочках (рис. 10).
Отметим, что при построении временных диаграмм, необходимо учесть то, что счётчик работает по отрицательному фронту (по спаду), а данные считываются по переднему фронту тактовой последовательности.
Рис.9 – Функциональная электрическая схема КРИ – 1/7 кодера
Рис.10 – Временные диаграммы, поясняющие принцип работы КРИ – 1/7
5. КОИ – 8/1 и КОИ – 7/1 соответственно кодера и декодера ССК будем выполнять в виде синхронных мультиплексоров на соответствующее число информационных и управляющих входов, а также формирователя сигналов управления мультиплексором, представляющего собой двоичный счётчик с дешифратором (“кольцевой” счётчик на “7”).
Функциональная электрическая схема КОИ – 7/1 представлена на рис.11, а временные диаграммы, поясняющие его принцип работы, приведены на рис. 12.
Для беспроводных технологий и других современных средств связи оптимальны простые высокоскоростные кодеры и декодеры (кодеки) помехоустойчивого кодирования с помехоустойчивостью, близкой к пределу Шеннона — пропускной способности канала (ПСК). Длина кода из-за роста скоростей не является важным ограничением. В [1, 2, 3] отмечены преимущества кодеков с малой плотностью проверок на четность (МПЧ) — Low Density Parity Check Codes (LDPC) на базе совершенных разностных множеств (СРМ), реализуемых на микросхемах. Отмечены недостатки часто рекламируемых кодеков алгоритмов Витерби (АВ), турбокодов (ТК) и кодов Рида — Соломона (КРС). У кодеков АВ, ТК и КРС скорости, энергопотребление и надежность более чем в 50 раз хуже, чем у рекомендованных в [1, 2, 3], при худшей помехозащите. С ростом скоростей передачи и энергозатрат растет интенсивность отказов, пропорциональная потребляемой энергии, которая является мерой старения аппаратуры [3]. Поэтому преимуществами высокой надежности обладают простые кодеки, реализованные на микросхемах. Однако до сих пор кодеки помехозащиты обычно реализуют на процессорах с надежностью в 20–30 раз худшей, и реже — на программируемых логических интегральных схемах (ПЛИС) с надежностью, худшей в четыре-пять раз, чем при реализации на специализированных микросхемах — Application Specified Integrated Circuit (ASIC). Цель этой работы — содействовать разработкам на микросхемах простейших и надежных кодеков с помехозащитой, близкой к ПСК (пределу Шеннона).
Первые оптимизированные пороговые кодеки (ОПД)
Впервые пороговые кодеки (ПК) сверточных кодов с МПЧ на двоичных регистрах сдвига (РС) с помехоустойчивостью, близкой к ПСК, были описаны в [4, 5, 6]. Их генераторные полиномы (ГП) с МПЧ, обладающие свойством «не более одного совпадения» (НБОС) позиций ненулевых членов ГП, подбирали «вручную». Поэтому ГП этих кодеков не были наилучшими. Решение в кодеках [4, 5, 6] формировали несколько итераций (ступеней) декодирования. Последовательно работали несколько анализаторов синдрома (АС) с увеличенными порогами в первых АС, снижающими вероятность ошибочных коррекций. Каждый следующий АС вносил поправки в решения предыдущих АС о коррекции информационных символов, приближая решение ПК к решению оптимального декодера (ОД). Были испытаны несколько таких оптимизированных пороговых декодеров (ОПД) с малыми кодовыми расстояниями d и длинами ГП кодов М. Поиск длинных ГП с кодами НБОС для реализации больших d был очень трудным, так как у ГП с НБОС длина М пропорциональна d2.
В [4] описаны ОПД с вероятностями ошибок канала (ВОК) — порогами, близкими к ПСК. Четыре кодека с кодовой скоростью R = 1/2 имели пять итераций (d = 7, 9, 11, 15 и M = 58, 107, 148, 201). Кодек с R = 3/4, d = 9 и М = 202 имел порог ВОК около 0,1. Кодек с R = 1/3, d = 13 и М = 202 имел шесть итераций и порог ВОК около 0,01. Наибольший эффект дают вторая и третья ступени АС. Обработка в ОПД квантованного решения улучшала энергетический выигрыш кодирования (ЭВК) на 1 дБ, но значительно усложняла ОПД. В [4] отмечены преимущества простоты и помехоустойчивости ОПД в сравнении с кодеками других видов.
В [5, 6] показаны преимущества внутреннего кодека ОПД в каскадных кодеках относительно других кодеков, включая кодеки самоортогональных кодов (СОК) и кодеки АВ. У ОПД с R = 1/2 ЭВК выше, чем у АВ, на 1,5 дБ при M = 360 и на 2,0 дБ при М = 1000. Отмечено, что в СОК с МПЧ, использующих проверочные матрицы, сходимость к решению ОД хуже и что появление микросхем с длинными РС существенно расширяет перспективы применения ОПД с РС на микросхемах. Отмечены преимущества прореживаний и удлинений ГП, которые снижают количество совпадающих вторых разностей и вероятность искажений синдрома ошибочными коррекциями. Удлинения ГП незначительно усложняют кодек, так как улучшают сходимость к решению ОД и позволяют снизить количество ступеней ОПД. Рассмотрено взаимодействие внутреннего кодека с модемом и показаны преимущества четырехпозиционной ФМ с неравномерной энергетикой канала (НЭК) — увеличением в два раза расстояний информационных символов, повышающим ЭВК кодека на 1 дБ. Показаны преимущества блоковых ОПД перед БЧХ и КРС в каскадных кодеках. У кодека со внутренним ОПД (R = 1/2, n = 160, М = 80, d = 7 и семь итераций) и внешним ОПД (R = 4/5, n = 880, M = 176, d = 7 и пять итераций) ЭВК больше на 2 дБ, чем у каскадных кодеков с БЧХ (28, 14, 4) и КРС (31, 25, 17) и на 0,8 дБ, чем у БЧХ (200, 100, 27) и КРС (511, 407, 105). Отмечено, что эти кодеки с БЧХ и КРС сложнее и медленнее каскадных кодеков ОПД. Очень сложные турбокоды (ТК) появились в 1993 г., и в [4–6] их сравнений с ОПД нет.
Преимущества кодеков с ОПД на базе СРМ
Совершенные разностные множества (СРМ), сохраняющие свойство НБОС при замыкании ГП «в кольцо» по модулю длины ГП, описаны в [7, 8]. Но они стали известными после окончания работ [4–6]. Если количество единиц в СРМ = N, то длина кода M = N(N–1)+1 и кодовое расстояние d = N+1. Разности позиций единиц СРМ по модулю М принимают каждое из значений последовательности 1, 2, 3, …N, N+1, …N(N–1) один раз. Особенности построения СРМ показаны в [8]. Там же приведена таблица 5.1 СРМ с N =<98 и М =<9507. В кодеках с СРМ удобно осуществлять прореживание ГП, которое снижает d, но улучшает сходимость к оптимальному решению. Коды с СРМ удобны для блоковых кодеков ОПД с несколькими циклами анализа в одной ступени решения. В них информация о каждом откорректированном в АС информационном символе — «единица коррекции» (ЕК) — поступает в память единиц коррекций (ПЕК), например в кольцевой регистр коррекций (КРК), откуда ЕК поступают в следующем цикле анализа в АС с неизменным порогом, облегчая отказ от ошибочной коррекции. Такой блоковый ОПД с КРК и одной ступенью может быть проще многоступенчатого сверточного ОПД с равной помехоустойчивостью. Отмечено, что все узлы кодеков ОПД с РС (кодер, АС, КРК) удобны для реализации на специализированной микросхеме (ASIC).
В [9] дан вывод о преимуществах блоковых кодеков ОПД для применения в пакетной связи. Отмечены преимущества НЭК. Приведена структурная схема сверточного МПЧ-кодека ОПД с R=4/5 и тремя итерациями, где каждая ступень АС высылает ЕК в ПЕК, откуда ЕК поступают в следующий АС, облегчая отказ от предыдущей коррекции. Отмечены преимущества пороговых элементов на КМОП-переключателях. Описаны несколько вариантов приближения помехоустойчивости ОПД к решению ОД. Полезно завысить порог в первом АС. Полезно из СРМ с избыточной в два-три раза длиной выбрать ГП, прореженный в два-три раза. Можно «растянуть» код СРМ в b раз (b = >N) с добавлением к каждой степени этого кода одного члена ряда 0, 1, 2, …(b–1). У таких «удлиненных» ГП меньше количество совпадающих вторых разностей, существенно снижена вероятность ошибочных коррекций, помехоустойчивость приближена к ОД. Но длина кода у таких кодеков растет почти как d3. Можно при СРМ ослабить размножение ошибок и приблизить решение кодеков ОПД к решению ОД, используя нестационарные ГП — поочередно кодируя информационные биты двумя и более разными ГП с циклическими сдвигами СРМ. У них длина растет медленнее, чем d3. В [10] также отмечены преимущества прореживания ГП и приближения решений ОПД к решению ОД и реализации всех узлов ОПД на микросхеме.
В [11] отмечены перспективы «перемешиваемых» нестационарных кодов, но они в этой работе использованы не были. Описан рекуррентный пороговый кодек ОПД, в котором из СРМ с N = 34, d = 35 и длиной М = 1123 по критерию наилучшего спектра весов вторых разностей выбран ГП с d = 13 и N = 12 на позициях: 1, 8, 60, 90, 193, 254, 399, 508, 840, 904, 935, 939. Такое прореживание (в 8,5 раза) и неравномерная энергетика канала, рекомендованные в [5], позволили получить высокую помехоустойчивость. Кодек работал в канале с АБГШ (аддитивный белый гауссовский шум) при Eb/Nо около 2,5 дБ. Количество ступеней итераций не указано. ЭВК у него выше, чем у кодека АВ, на 1,5–2,0 дБ.
Отмеченные преимущества ОПД были использованы в микросхемах кодеков, описанных в [1–3]. В [3] упомянута микросхема блокового кодека с ОПД на базе СРМ длиной M = 553, работавшая в радиоканале челнока «Буран» (1988 г.), реализованная на матричной БИС (МБИС) серии 1515 ХМ1 емкостью 3 тыс. условных вентилей (УВ) и проектной нормой (ПН) 5 мкм. У этого кодека кодовая скорость R = 1/2, N = 24 и d = 25. Использовать более длинный ГП не позволила малая емкость кристалла МБИС. Помехоустойчивость кодека с жестким решением канала на этой МБИС лучше, чем у значительно более сложного кодека АВ с мягким решением. Эта МБИС может работать в режимах кодера, АС и КРК. Благодаря СРМ блоковый ОПД с такой МБИС может использовать только одну ступень — один АС, работающий вместе с КРК.
Для Минобороны была разработана (совместно с компанией «Вигстар» и МИЭТ, Зеленоград) МБИС 5503ХМ7-158 [12] с ПН 1,5 мкм — рекуррентный (сверточный) высокоскоростной (до 15 Мбит/с) кодек на базе совершенного разностного множества (СРМ-133) с кодовой скоростью R = 1/2 на нестационарных ГП с двумя ветвями кода [12]. Его сложность — 5,0 тыс. УВ. Энергопотребление — около 20 мкДж/бит. Кодек работал с жестким решением. Он устойчив к большим помехам. Его синхронизация устойчива даже при действии плотного (до 50%) пакета ошибок длиной до 25 бит. Это преимущество представляет особенную ценность для защиты от заградительных помех [1–3]. В [13] показано, что ведущие зарубежные фирмы (Intel, Motorola, Samsung и др.) более 15 лет реализуют сверхширокополосные связи (СШПС) на микросхемах system-on-chip (SoC) — система на кристалле (СнК) собственной разработки. В [1] отмечено, что многие российские фирмы уже в 2011 г. создали аппаратуру на SoC емкостью более 10 млн УВ. Такая емкость позволяет реализовать на отечественных микросхемах кодеки с ОПД на прореженных ГП, а также на «b-преобразованных» ГП длиной более 1 млн бит с помехоустойчивостью, совпадающей практически с ОД — пропускной способностью канала.
Многопороговые декодеры самоортогональных кодов
За последние 30 лет появилось много работ по кодекам с малой плотностью проверок на четность (МПЧ), продолжающих работы по самоортогональным кодам СОК [14, 15], где описаны матричные декодеры квазициклических кодов (quasy-cyclic code) с переменными порогами. В первых строках матрицы содержат СРМ — perfect difference sets. Анализ матриц ведут с помощью графа Таннера, и преимущества СРМ не используют надлежащим образом. Среди этих работ наибольший интерес представляют исследования путей улучшения СОК на базе многопороговых декодеров (МПД), итоги которых описаны в [16–19]. В них основное внимание уделено программной реализации недвоичных МПД СОК.
В [16] упомянуты преимущества НЭК и длинных кодов (несколько тысяч бит) с 10–20 итерациями, но не упомянуты рекомендации [5]
по алгоритмам удлинений ГП и НЭК. Даны рекомендации по устаревшим алгоритмам недвоичных qСОК с q = 8, удобным для программной, но не для аппаратной реализации. Наиболее интересен блоковый кодек, выполненный подобно ОПД [4–6, 9–12] на двоичных РС. В этом кодеке один фиксированный порог и нет матриц СОК, но он ошибочно назван «многопороговым СОК». В кодеке работает кольцевой регистр коррекций (КРК) с неудачным названием «разностный регистр». В него вводят единицы коррекций (ЕК), которые в следующем цикле поступают на порог, облегчая отказы от ошибочных коррекций. В кодеке использован короткий ГП на СРМ-13 без прореживаний с R = 1/2, N= 6, d = 7, М = 13. Упоминания о СРМ нет. Этот ГП заимствован из [8], но такой ссылки нет.
В [17] дан обзор методов помехоустойчивого кодирования и отмечено, что вблизи ПСК могут работать кодеки трех типов — турбокодеки (ТК), кодеки МПЧ-LDPC и кодеки МПД СОК. Как наилучшие отмечены блоковые кодеки МПЧ-LDPC, задаваемые проверочными матрицами, у которых синдром анализируют в соответствии с графом Таннера алгоритмами sum-product или min-sum. Отмечено, что помехоустойчивость LDPC при длине кода около 106 всего на 0,1 дБ отстоит от ПСК — предела Шеннона, и что ЭВК у кодеков МПД СОК меньше, чем у кодеков LDPC. При 40 итерациях МПД СОК с кодами длиной около 40 тыс. отстоят от ПСК на 2 дБ, и не отмечено, что кодеки МПД СОК очень сложны для аппаратной реализации.
В [18] рассмотрены кодеки СОК с МПЧ, с параллельным каскадированием и проверочными матрицами с разреженной структурой. Приведен пример графа Таннера с малым количеством ребер для блокового СОК длиной 26 бит на базе СРМ-13 с ГП (0, 1, 4, 6) и одной ступенью. Описаны два кодека МПД СОК, реализованные на ПЛИС. Декодер на первой ПЛИС Spartan-II имеет сложность около 0,2 млн вентилей, задержку декодирования 10 000 бит, R = 1/2, ЭВК более 6,5 дБ и ВО декодирования около 10–5 при Eb/Nо = 2,9 дБ. Декодер на второй ПЛИС Altera сложнее. При 40 итерациях он имеет ЭВК более 7,5 дБ при ВОК (вероятности ошибок канала) декодирования около 10–5 и Eb/Nо около 1,9 дБ. Рассмотрены двоичные каскадные коды на РС, подобные описанным в [5, 6], но без этих ссылок. Описан тот же, что и в [16], блоковый кодек ОПД на РС с СРМ-13 с КРК — «разностным регистром». Для параллельного каскадирования недвоичных СОК рекомендованы декодеры с алгоритмом min-sum, без критики сложности его аппаратной реализации.
В [19] содержатся итоги более 30 лет исследований кодеков МПД СОК. Приведены ошибочные выводы, что «задача исправлять проще, быстрее и при более высоком уровне шума еще очень далека от окончательного решения» и что характеристики кодеков невозможно приблизить к ПСК «при любом числе итераций в блоковом МПД или сколь угодно длинной цепочке в сверточном МПД». С ними нельзя согласиться. Полезно напомнить о методах ОПД, у которых есть такие возможности. Ведь МПД СОК на двоичных РС фактически утратили отличия от описанных ОПД. Описан двухступенчатый сверточный кодек с разными порогами без ПЕК, подобный ОПД [4–6], но ссылок нет. Отмечены трудности поиска хороших кодов и преимущества «чрезвычайно длинных кодов» для d =<41 и кодов с «переменными связями», но нет ссылок на [5, 6, 9, 11], где предложены удлиненные и нестационарные ГП. Рекомендаций по методам удлинения ГП нет. Упомянут кодек на ПЛИС с 40 итерациями длиной около 1 млн бит, но не описана его структура и генераторный полином. Повторено ошибочное утверждение, что распараллеливание операций упростит аппаратную реализацию МПД СОК. В действительности у параллельных архитектур сложны трассировки соединений между блоками вычислений и поэтому резко возрастает уровень потребления и интенсивность отказов кодека. Распараллеливание и сложные трассировки — это ошибки, серьезно препятствующие реализации на микросхеме. В выводах рекомендован поиск хороших длинных ГП для блоковых кодов МПД СОК без упоминания методов удлинения, описанных в [5, 6, 9, 11], удобных также для блоковых кодов.
Наибольшее внимание в [16–19] уделено кодам с МПД qСОК с синдромами на матрицах, у которых сходимость к решению ОД хуже, область оптимизации меньше, и они значительно сложнее ОПД на двоичных РС. Очевидно, что МПД с qСОК — тупиковый путь. Основным недостатком работ [16–19] является опора на программные средства реализации и игнорирование преимуществ реализации кодеков на микросхемах. Алгоритмов МПД СОК, пригодных для современных средств реализации на микросхемах, в [16–19] нет. Вряд ли кодеки МПД СОК будут реализованы на микросхемах.
Особенности матричных кодеков c МПЧ-LDPC
Коды c малой плотностью проверок на четность — low density parity check codes (LDPC) с матрицами проверок и их использование в системах передачи информации рассмотрены во многих работах. Отмечены перспективность применения МПЧ-LDPC-кодов и их преимущества в сравнении с другими кодами. Особенностью (и недостатком) этих работ являются программные средства реализации LDPC-кодов и игнорирование аппаратной реализации на микросхемах. В матричных кодеках LDPC, подобно МПД СОК, используют итеративное декодирование, а синдром формируют или в соответствии с графом Таннера, или по алгоритмам sum-product и min-sum, которые также сложны. Но характеристики у кодеков LDPC с длинными ГП лучше, чем у кодеков МПД СОК.
В [21] описаны два матричных кодека LDPC. Длинный кодек, отстоящий от ПСК на 0,0045 дБ, не описан. По-видимому, его длина более 108. Кодек с R = 1/2, d = 200 и длиной информационного блока 107 отстоит от предела Шеннона на 0,04 дБ. В нем использовано декодирование по алгоритму sum-product и более 800 итераций. В [22] описан матричный LDPC-кодек на ПЛИС и его испытания в канале с АБГШ. В нем использован алгоритм sum-product. Заверения об «экономии аппаратных ресурсов» при реализации матричных LDPC-кодеков на ПЛИС не обоснованы. В [23] дан анализ трех типов недвоичных кодеков LDPC и кодеков Рида — Соломона (КРС) разной длины и показано, что при ВОК декодирования 10–5 и близких R преимущества помехоустойчивости LDPC перед КРС при коротких блоках — 1,6 дБ, при средних — 2,0 дБ, при длинных — 2,4 дБ.
Реализация кодеков LDPC на двоичных регистрах сдвига
Заключение
Постановление Правительства [20] требует разработок на микросхемах аппаратуры, конкурентной на мировом уровне. В нем п. 66 предусматривает освоение проектных норм микросхем, близких к зарубежным. В 2015 г. будут освоены ПН 0,045 мкм, позволяющие реализовать емкости кристалла более 20 млн УВ. Поставлена задача (п. 137) увеличить на базе ПН 0,045 мкм скорости обмена и передачи информации до 30 Гбит/с. Такая скорость доступна только для кодеков с ОПД на двоичных РС и недоступна для матричных алгоритмов, используемых в LDPC и МПД СОК. Но выбор сложных неэффективных алгоритмов помехоустойчивого кодирования нельзя объяснять некомпетентностью заказчиков и разработчиков.
Главная причина — следование зарубежным рекомендациям, что облегчало публикации, как это было с кодеками АВ, ТК и КРС. Вторая причина — следование привычным, но ошибочным критериям программной сложности. Возможно, что эта статья поможет остановить разработки кодеков на процессорах и ПЛИС и разработать на отечественных микросхемах близкие к пределу Шеннона кодеки с ОПД, конкурентные на мировом уровне. Ожидаемая сложность, энергопотребление и цена у них будут на порядок ниже, а надежность — на порядок выше, чем у рекламируемых матричных МПД СОК и матричных LDPC-кодеков.
Читайте также: