Основные сведения о сверточных кодах с алгоритмом порогового декодирования

В общем виде кодирование информации СК может быть представлено следующим образом:

(1.1).

j=1…k0, i=j+1,.

где I (x) — последовательность передаваемых информационных символов;

x — оператор задержки;

g(x) — порождающий или образующий полином (многочлен);

ko — блок информационных символов, одновременно поступающих на вход кодирующего устройства (k0?1).

Способ формирования кодовых символов, выполняемых согласно (1.1), соответствует форме записи свёртки двух функций, что и послужило названию данных кодов. Свёрточный код — это рекуррентный код с периодической полубесконечной структурой символов кодовой последовательности. Обобщённая структурная схема кодера СК имеет следующий вид, представленный на рисунке 1.1:

Рисунок 1.1 — Обобщённая структурная схема кодера.

Входные информационные символы I (x) делятся на k0 символов, которые одновременно с каждым тактом поступают на входы кодера СК, в котором согласно (1) формируются n0 кодовых символов. Таким образом, кодовая последовательность T⁽ⁱ⁾⁽x) представляет собой полубесконечную последовательность блоков n0.

В высокоскоростных (В? 17,184 Мбит/с) цифровых системах связи широкое применение получили свёрточные коды с алгоритмом порогового декодирования (ПД). ПД сверточных кодов позволяет значительно упростить схемные реализации кодеков при коррекции как независимых, так и пакетов ошибок. Наибольшей простотой реализации отличаются самоортогональные сверточные коды (ССК).

ССК — это коды, у которых декодируемый информационный символ входит одновременно во всех проверочных уровнях, а все остальные символы, участвующие в декодировании в данный момент времени, входят не более, чем в одно проверочное уравнение, т. е. СКК формирует, так называемую, систему раздельных проверок.

К основным характеристикам ССК относятся:

• 1. Длина миниблока информационных символов (количество информационных подпотоков, на которое распределяется входной информационный поток (I (D))) — k0;
• 2. Длина миниблока кодовых символов — n0;
• 3. Скорость передачи кода, определяемая соотношением:

(1.2).

Она характеризует избыточность, вводимую при кодировании. Большие скорости кода позволяют увеличить пропускную способность канала связи, зато снижение скорости уменьшает количество ошибок на выходе приёмника.

4. Относительная избыточность кода:

(1.3).

• 5. Количество ортогональных проверочных уравнений кода — J;
• 6. Кратность или колличество исправляемых ошибок:

(1.4).

7. Минимальное кодовое расстояние кода:

(1.5).

• 8. Максимальная степень порождающего полинома g (x) — m;
• 9. Память кода, называемая также входной длиной кодового ограничения или информационной длиной кодового слова, соответствующая кодированию информационных блоков из k0 символов в течение (m+1) тактов:

(1.6).

Определяется максимальной степенью порождающего многочлена.

10. Кратность обнаруживаемых ошибок:

11. Эффективная длина кодового ограничения:

(1.8).

12. Вероятность безошибочного декодирования ССК, определяемая по формуле:

(1.9).

где d₀ — минимальное кодовое расстояние ССК;

р_k — исходная вероятность ошибки в канале связи;

q=1-p_k

• — вероятность безошибочного приема в канале связи.
• 13. Достоверность передаваемой информации при использовании ССК точнее оценивается вероятностью первой ошибки декодирования, определяемой по формуле :

(1.10).

где t — кратность исправляемых ошибок;

— эффективная длина кодового ограничения;

р_k — исходная вероятность ошибки на выходе модема или канала связи;

q = 1-p_k

— вероятность безошибочного приема информации.

Для порогового декодирования вероятность ошибочного декодирования в первом символе P_1e является нижней оценкой средней вероятности ошибки P_ср.

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

ССК задаются следующей порождающей матрицей G:

(1.11).

Или.

(1.12).

Для ССК с алгоритмом порогового декодирования проверочная матрица H задается следующим образом:

Из данной проверочной матрицы следует, что для ССК с.

проверочная матрица Н содержит (n0-k0) строк и k0 столбцов проверочных треугольников. Для ССК с.

.

n0= 2;3;…,.

проверочная матрица Н содержит k0=1, т. е. один столбец и (n0-1) строк проверочных треугольников.

Каждый из проверочных треугольников Нi, k0+i, i=1,2, …; k0=1,2, …, проверочной матрицы Н в общем случае имеет вид:

(1.14).

где q — коэффициенты, равные либо 1, либо 0; j, i — номера соответственно строки и столбца матрицы Н, которыми определяется проверочный треугольник; 0, …m — порядковые номера степеней, в которые возводятся соответствующие коэффициенты порождающего полинома.

Основную информацию о самоортогональных сверточных кодах ССК несут коэффициенты левого столбца и нижней строки проверочного треугольника.

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

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

R = k0/n0.

количество разностных треугольников равно числу k0. Для всех разностных треугольников общим числом является «0», который не указывается в совокупности чисел, однако учитывается при выборе степеней ненулевых членов порождающих полиномов. Очевидно, что число «0» определяет нулевую степень первых ненулевых членов порождающих полиномов. Степени ненулевых членов порождающих полиномов по заданным или построенным разностным треугольникам можно найти путем выбора чисел: левого крайнего столбца разностного треугольника, считывая их сверху вниз и дополняя числом «0», или верхней строки разностного треугольника в такой последовательности: первое число — показатель степени второго ненулевого члена порождающего полинома; суммирование первого и второго чисел первой строки разностного треугольника определяет показатель степени третьего ненулевого члена порождающего полинома и т. д.

Разностный треугольник ССК может быть построен, если задан проверочный треугольник, и наоборот. Например, используя проверочный треугольник (1.15) можно построить разностный треугольник, следующим образом:

(1.15).

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

• 3−1=2
• (3 — номер позиции третьей строки; 1 — номер позиции первой строки);
• 6−1=5

И.

7−1=6.

Для получения чисел второго столбца за вычитаемое берем номер позиции третьей строки:

6−3=3.

И.

7−3=4.

Для получения чисел третьего столбца за вычитаемое берем номер позиции шестой строки:

7−8=1.

В итоге получаем следующий разностный треугольник:

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

Пороговое декодирование ССК обеспечивается алгоритмом формирования системы J (J2) проверочных уравнений (проверок), а именно: система проверок формируется таким образом, что декодируемый информационный символ входит во все проверки, а все остальные символы входят только в одну проверку (проверочное уравнение). Для этого следует использовать транспонированную проверочную матрицу, имеющую вид:

(1.16).

где Нm — проверочный треугольник; Im — единичная матрица.

Например, для ССК, задаваемого полиномом.

g (x)=1+x²+x⁵+x⁶, Н^T7

выглядит следующим образом:

(1.17).

Из матрицы (1.17) система J ортогональных проверок имеет вид:

S0=Eⁱ⁰+E^P0,.

S2=Eⁱ⁰+ Eⁱ² +E^P2, (18).

S5=Eⁱ⁰+ Eⁱ³ + Eⁱ⁵ +E^P5,

S6=Eⁱ⁰ + Eⁱ¹ + Eⁱ⁴ + E^P6.

Поскольку столбцы матрицы (1.17), соответствующие ненулевым двоичным символам последней строки, не имеют ни одной общей строки (кроме последней строки), в которой имели бы общий ненулевой символ, то эти столбцы и система проверок (1.18) ортогональны относительно декодируемого информационного символа. Следовательно, ненулевые двоичные символы последней строки матрицы (1.17) соответствуют символам, участвующим в вычислении синдрома, и поэтому в качестве системы J проверок (1.18) можно использовать символы синдрома, а не линейные комбинации проверок. Это упрощает реализацию алгоритма порогового декодирования ССК.

Отметим, что количество ортогональных проверок J равно числу строк или столбцов, которые начинаются с ненулевых двоичных символов, а размерность проверок определяется количеством ненулевых символов, входящих в строку.

При пороговом декодировании свёрточных кодов вычисляются синдромы (признаки места ошибочных символов), затем эти синдромы или последовательности, полученные посредством линейного преобразования синдромов, подаются на вход порогового элемента. Число пороговых элементов (ПЭ) равно к0, т. е. количеству одновременно декодируемых информационных символов. Число входов каждого ПЭ равно числу ортогональных проверок J. Минимальное число входных символов ПЭ, отличных от нуля и необходимых для принятия решения ПЭ о значении декодируемого символа, называется порогом.

Декодер ССК должен реализовывать следующие операции:

распределять символы принятой кодовой последовательности Т`(х) на n₀ потоков, что реализуется демультиплексором;

формировать последовательность проверочных символов из принятых информационных символов Iпр (x) (устройство, аналогичное кодеру);

формировать последовательность синдромных символов

S (x)=Р`_пр(х)Р_сф(х);

производить анализ

N=m+1

символов синдрома или проверку Jk₀ ортогональных проверочных уравнений на четность;

осуществлять коррекцию информационных и синдромных символов.

При пороговом декодировании с использованием обратной связи одновременно с декодированием информационных символов происходит коррекция синдромных символов, использованных при формировании сигнала коррекции. Это выполняется с целью устранения влияния ненулевых символов S (x) на правильное принятие решения при декодировании последующих информационных символов.

В общем случае ПД ССК имеют следующие преимущества:

• — простоту реализации;
• — большое количество кодов;
• — способность работать в каналах связи, как с независимыми, так и с пакетами ошибок;
• — способность работы на очень высоких скоростях передачи информации;
• — гарантированная исправляющая способность на длине кодового ограничения;

Недостатками ПД ССК являются:

• — уменьшение количества числа кодов с требуемой корректирующей способности при увеличении скорости кода;
• — сложность реализации кодека с увеличением скорости кода;
• — уменьшение исправляющей способности кодов с увеличением скорости кода;
• — размножение ошибок на выходе декодера при возникновении в канале связи ошибок, превышающих корректирующую способность выбранного кода.