Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Граница Хэмминга

Граница Хэмминга устанавливает предельную эффективность, т. степень использования пространства всех возможных кодовых слов, для кода, исправляющего ошибки.

Теорема (граница Хэмминга)

Пусть означает мощность (количество кодовых слов) блочного кода над -ичным алфавитом с блоком длины и кодовым расстоянием (d_0 = d). Тогда, где – биномиальный коэффициент,

Граница Варшамова-Гилберта

Граница Варшамова-Гилберта устанавливает нижнюю границу количества элементов в исправляющем ошибки коде, т. ставит границу сверху на максимальное число дополнительных “проверочных” бит.

Теорема (граница Варшамова-Гилберта)

Пусть означает максимальную мощность (количество кодовых слов) для любого блочного кода над -ичным алфавитом с блоком длины и кодовым расстоянием (d_0 = d). Тогда, где – биномиальный коэффициент.

Тогда, для любого (x in mathbb F_q^n) ((mathbb F_q^n) – множество всех (q)-ичных векторов длины (n)), существует хотя бы одно кодовое слово (c_x in C): (d_H(x, c_x) le d-1. ) В противном случае, мы могли бы добавить (x) в код, сохранив все его свойства, что противоречит предположению о его максимальной мощности.

Перефразируя утверждение теоремы, получаем

Совершенные коды

Любой исправляющий ошибки код, таким образом, удовлетворяет неравенствам:

Коды, удовлетворяющие этому равенству называются совершенными.

Использование совершенных кодов с возрастающей длиной блока позволило бы сколь угодно близко подходить к пределу Шеннона. Однако, есть одна проблема: совершенных кодов крайне мало.

Собственно, все существующие нетривиальные совершенные коды над двоичным алфавитом можно перечислить:

  • Коды Хэмминга для
  • Повторные коды, т.е. коды, раз посылающие сообщение, с нечётным и (t = (N-1)/2).
  • Совершенный двоичный код Голея с , имеющий длину кодового слова , “полезную нагрузку” (I_C = 12) и .

Кодовое расстояние и корректирующая способность кода

Под корректирующей способностью кодапонимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q. Корректирующая способность кода связана с его кодовым расстоянием.

Расстояниемdij между кодами(кодовыми комбинациями) i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

Кодовым расстояниемd для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

где i≠j, i=1,m; j=1,m.

Пусть есть кодовая таблица:

Исходные символы
Двоичные коды
a

b

c

d

Тогда расстояния между кодовыми комбинациями имеют значения:

dab = 1; dad = 2; dbd = 1; dac = 1; dbc = 2; dcd = 1.

Это означает, что всякая ошибка кратности 1 (и более) переводит исходную кодовую комбинацию в другую кодовую комбинацию, которая также принадлежит коду.

Увеличить кодовое расстояние можно, введя в кодовые комбинации дополнительный разряд (или разряды). Тогда исходные разряды называют информационными, а дополнительный (или дополнительные) – проверочным(проверочными).

Значение одного проверочного разряда в простейшем случае определяется как результат суммирования по модулю 2 информационных разрядов.

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

Исходные символы
Информационные разряды кода
Проверочный разряд кода
Результирующий код
a

b

c

d

Таким образом, полученный код является трехразрядным.

Определим кодовое расстояние полученного кода. Для этого вначале выясним расстояния между кодовыми комбинациями:

dab = 2; dad = 2; dbd = 2; dac = 2; dbc = 2; dcd = 2.

Пусть передается кодовая комбинация, соответствующая символу c, – 101. Пусть на нее накладывается ошибка кратности 1. Возможные результаты искажения приведены в таблице:

Передаваемая кодовая комбинация
Ошибка
Принимаемая кодовая комбинация
Результат декодирования

Невозможно декодировать

То же

“-“

В результате данной ошибки получаемые кодовые комбинации невозможно декодировать, так как они отсутствуют в результирующем коде (см. таблицу выше).

Корректирующая способность кода основана также на понятиях разрешенных и запрещенных кодовых комбинаций.

Разрешенными кодовыми комбинациями называются те, которые присутствуют в исходной кодовой таблице. Например, если сформирован код

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

Запрещенные кодовые комбинации – это те, которые отсутствуют в исходной кодовой таблице. Их количество определяется по формуле: 2r – m, где r – общее число двоичных разрядов (информационные плюс проверочные) в коде.

Сформируем все разрешенные и запрещенные кодовые комбинации для кода из приведенной выше таблицы, при этом используем схему формирования кода Грея:

a
 

 
b

d
 

 
c

Здесь обозначения строк – значения графы Информационные разряды кода, обозначения столбцов – значения проверочных разрядов. Пустые ячейки означают запрещенные кодовые комбинации.

Как видно из последней таблицы, отстояние кодовых комбинаций для исходных символов a, b, c, d равно двум разрядам:

· символы, находящиеся в одном столбце (a и d, b и c), имеют одинаковый проверочный разряд, но находятся в несмежных строках, которые различаются двумя разрядами;

· символы, находящиеся в смежных строках (a и b, b и d, d и c), которые различаются одним разрядом, расположены попарно в разных столбцах, имеющих различное обозначение.

Поэтому при наличии ошибки кратности 1 кодовая комбинация переходит в соседнюю запрещенную.

Очевидно, коды, построенные по схеме рис. 3, не позволяют обнаружить ошибку кратности 2: в самом деле, при этом кодовая комбинация переходит в другую разрешенную кодовую комбинацию.

Существует связь между кодовым расстоянием d и минимальной кратностью ошибки q, которую код может обнаруживать:

Пример 1. На базе кода из таблицы построить код, обнаруживающий ошибки кратности 2.

Для решения задачи воспользуемся схемой формирования кода Грея с некоторыми модификациями.

Поскольку код для обнаружения ошибки кратностью 1 построен, используем его для обозначения строк схемы, причем с каждой строкой свяжем символ, который соответствует данной кодовой комбинации: так с первой строкой свяжем символ a, со второй – b и т. Очевидно, кодовые комбинации в обозначении строк схемы различаются двумя разрядами.

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

С учетом сделанных замечаний схема имеет 4 столбца и 4 строки и представлена ниже:

a
 
 
 

 
b
 
 

 
 
d
 

 
 
 
c

Таким образом, построен следующий код:

Проверим, обнаруживает ли построенный код ошибку кратности 2. Для этого зададимся произвольной кодовой комбинацией, например, 01101 (символ b). Результат проверок приведен в таблице:

Передаваемая кодовая комбинация
Ошибка
Принимаемая кодовая комбинация
Результат декодирования

Невозможно декодировать

То же

“-”

“-”

“-”

“-”

“-”

“-”

“-”

“-“

Таким образом, задача решена.

Разделимые коды с обнаружением ошибок

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

Правила образования этих кодов ясны из приводимой ниже таблицы.

N0
Примитивный безизбыточный код
Код с проверкой на нечетность
Код с простым повторением
Инверсный код
Корреляционный код

000 1
000 000
000 000
01 01 01

001 0
001 001
001 110
01 01 10

010 0
010 010
010 101
01 10 01

011 1
011 011
011 011
01 10 10

100 0
100 100
100 011
10 01 01

101 1
101 101
101 101
10 01 10

110 1
110 110
110 110
10 10 01

111 0
111 111
111 000
10 10 10

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

Этот код обнаруживает все ошибки нечетной кратности. Мощность кода Np = 2n-1. Коэффициент избыточности , т. уменьшается с увеличением числа разрядов кодовой комбинации.

Для разделимых равномерных двоичных кодов формулу для коэффициента избыточности можно упростить :

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

где n – общее число разрядов в кодовой комбинации, k- число информационных разрядов в кодовой комбинации.

При приеме кода с простым повторением осуществляется сравнение k информационных разрядов комбинации с остальными n-k контрольными разрядами. Если значения сравниваемых одноименных разрядов совпадают, то комбинация полагается принятой верно. В противном случае реализуется защитный отказ. Этот код обнаруживает все ошибки нечетной кратности и часть ошибок четной кратности. Мощность кода Np = 2n/2. Коэффициент избыточности.

Прием инверсного кода осуществляется в два этапа. На первом этапе анализируется четность информационной части комбинации. Если она четна, то проверочная часть остается без изменения. Если она нечетна, то проверочная часть инвертируется. На втором этапе информационная часть поразрядно сравнивается с проверочной. Если они совпадают, то полагается, что комбинация принята верно. Этот код обнаруживает все ошибки кратностью 1,2,5,6 и большую часть 3- и 4-кратных ошибок. Мощность кода и коэффициент избыточности имеют те же значения, что и для кода с простым повторением.

При приеме корреляционного кода сравниваются парные элементы кодовой комбинации. Если хотя бы в одном случае они совпадают, принимается решение об ошибочно принятой комбинации. Характеристики кода полностью совпадают с характеристиками кода с простым повторением.

9-1. Что называется кодированием в широком смысле?

9-2. Что называется алфавитом источника?

9-3. Что называется объемом алфавита источника?

9-4. Что называется кодированием в узком смысле?

9-5. Что называется кодовой комбинацией?

9-6. Что называется кодом?

9-7. Что называется основанием кода?

9-8. Какой код называется равномерным?

9-9. чем продиктована необходимость замены каждого символа источника совокупностью кодовых символов?

9-10. Какие комбинации кода называются разрешенными?

9-11. Что называется мощностью кода?

9-12. Что является численной характеристикой избыточности кода?

9-13. Какой код называется безизбыточным?

9-14. Почему безизбыточные коды не обладают помехоустойчивостью?

9-15. Какое кодирование называется помехоустойчивым?

9-16. Какие коды называются кодами с обнаружением ошибок?

9-17. Какие коды называются кодами с обнаружением ошибок?

9-18. Что называется кодовым расстоянием между двумя кодовыми комбинациями?

9-19. Какую операцию необходимо выполнить для определения кодового расстояния между двумя кодовыми комбинациями?

9-20. Что называется кодовым расстоянием кода?

9-21. Что называется вектором ошибки?

9-22. Что называется кратностью ошибки?

9-23. Перечислите параметры биномиального закона распределения кратности ошибок?

9-24. Как связаны кодовое расстояние кода и вероятность ошибочного декодирования?

9-25. Как связаны кодовое расстояние кода и кратность обнаруживаемых им ошибок?

9-26. Как связаны кодовое расстояние кода и кратность исправляемых им ошибок?

9-27. Какой избыточный код называется блоковым?

9-28. Какой избыточный код называется разделимым?

9-29. Какой разделимый избыточный код называется систематическим?

9-30. Почему большинство систематических разделимых кодов называются линейными?

9-31. Что называется спектром кода?

9-32. Что является характерной особенностью кодов, называемых циклическими?

9-33. Чему равна мощность кода на одно сочетание?

9-34. Как осуществляется декодирование кода на одно сочетание?

9-35. Является ли код на одно сочетание разделимым?

9-36. Как осуществляется декодирование кода с проверкой паритета?

9-37. Как определяется коэффициент избыточности для разделимых равномерных двоичных кодов?

9-38. Как осуществляется декодирование кода с простым повторением?

9-39. Как осуществляется декодирование инверсного кода?

9-40. Как осуществляется декодирование корреляционного кода?

Лекция 10. Коды с обобщенными проверками на четность

К групповым кодам с обнаружением и исправлением ошибок относятся коды с обобщенными проверками на четность и полиномиальные коды.

Все систематические коды являются разделимыми. Их принято иногда называть (n,k)-кодами, где n – общее число разрядов в кодовой комбинации, k- число информационных разрядов. Число контрольных разрядов в кодовой комбинации, следовательно, равно n-k.

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

Наиболее важными и полезными границами для кодового расстояния являются граница Хэмминга, граница Плоткина и граница Варшамова – Гилберта.

Читайте также:  Параметр ошибки 87 установлен неправильно Windows 10 VPN

Граница Хэмминга, выражаемая обычно следующим образом,

,
(3

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

Граница Плоткина также является верхней границей для кодового расстояния при данных n и k и может выражаться следующим образом

Выражение (3. 9) удобно для получения максимально возможного d при заданных n и k, но не очень удобно для получения максимального k при данных d и n, в связи с чем другая форма границы Плоткина выглядит следующим образом

Граница Хэмминга обычно близка к оптимальной для высокоскоростных кодов (т. для больших значений k/n), а граница Плоткина – для низкоскоростных кодов.

Согласно границе Варшамова – Гилберта, выражаемой как

существует (n,k)-код с кодовым расстоянием, не меньшим d , и с числом проверок на четность, не превышающим n-k. Таким образом, граница Варшамова – Гилберта является границей существования и дает нижнюю оценку для кодового расстояния «наилучшего» кода.

Приведем пример использования этих границ. Предположим, что требуется найти код длиной n=63 с кодовым расстоянием d=5 и наибольшим возможным значением k. Примером такого кода является (63,51)-код БЧХ. Для оценки того, насколько хорошим является этот код, используем границы Хэмминга и Варшамова – Гилберта. Из (3. 8) следует, что 2017 £ 2n-k , откуда n-k ³11.

Граница Варшамова – Гилберта (3. 11) «утверждает», что 39774>2n-k, откуда n-k £16. Таким образом, из границы Хэмминга следует, что не существует кодов, обеспечивающих заданные параметры, с n-k<11, а граница Варшамова – Гилберта гарантирует существование таких кодов с n-k£16. Отсюда можно сделать вывод, что код (63,51) является «хорошим» и дальнейшие поиски могут привести лишь к незначительному улучшению.

Для кодов с d=3 для определения требуемого числа контрольных разрядов можно найти более простое выражение, воспользовавшись следующими рассуждениями. При передаче кодовой комбинации может быть искажен любой из n разрядов комбинации или комбинация принята без искажений. Следовательно, всего может быть n+1 вариантов исхода. Использование контрольных разрядов должно обеспечить возможность различения всех n+1 вариантов. С помощью n-k разрядов можно описать 2n-k событий, следовательно, должно выполняться условие или

Рассматриваемые (n,k)-коды называются групповыми. Своим названием они обязаны тому, что множество кодовых комбинаций вместе с нулевой кодовой комбинацией, снабженное операцией посимвольного сложения по модулю два, образуют математическую структуру, называемую группой. Основные свойства группы:

1) замкнутость – т. сумма по модулю два двух элементов группы всегда лежит в группе,

2) ассоциативность – т. (aÅb)Åc=aÅ(bÅc),

3) наличие единичного элемента – для двоичных кодов это нулевая комбинация,

4) каждый элемент группы обладает обратным, для которого а+(-а)=0, для двоичных кодов каждая кодовая комбинация совпадает со своей обратной.

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

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

Пусть кодовая комбинация двоичного группового кода имеет n разрядов: unun-1un-2. Положим, что среди этих n разрядов символы ur, ul, us – контрольные. Число проверочных уравнений определяется числом контрольных символов:

В этих уравнениях коэффициенты принимают значения 1 или 0 в зависимости от того, используется или нет соответственно для определения значения i-го контрольного разряда j-й информационный разряд.

С помощью этих уравнений могут быть составлены все Np=2k разрешенных или рабочих комбинаций кода путем записи информационных разрядов каждой комбинации и вычисления значений контрольных разрядов по уравнениям (3. 13) для каждой комбинации информационных разрядов. Таким образом, тот или иной код может быть задан таблицей информационных кодовых комбинаций и системой проверочных уравнений.

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

Удобно в качестве образующих выбрать комбинации, которые содержать лишь по одной единице в информационных разрядах. Следовательно, число таких комбинаций равно k – числу информационных разрядов. Если к тому же упорядочить разряды, расположив слева направо сначала информационные разряды, начиная со старшего, а затем контрольные разряды, и записать упорядоченные таким образом комбинации одна под другой, то получим матрицу, содержащую n столбцов и k строк, которая называется образующей матрицей систематического (n,k)-кода и обозначается Gn,k.

Пример. Построить образующую матрицу (7,4)-кода, имеющего следующие проверочные уравнения

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Решение. Сначала целесообразно построить полную таблицу кода в соответствии с проверочными уравнениями.

a4
a3
a2
a1
b3
b2
b1

Выберем образующие кодовые комбинации (выделены жирным шрифтом) и запишем их в виде образующей матрицы.

При наличии образующей матрицы можно найти все остальные кодовые комбинации кода без использования полной таблицы кода. Например, требуется найти кодовую комбинацию для информационной комбинации 1101. Для этого нужно суммировать по модулю два три соответствующих строки образующей матрицы:

после чего можно сопоставить результат с полной таблицей кода.

Анализ вида образующей матрицы приводит к выводу, что она состоит из двух матриц – единичной

и дополняющей.

Обобщая рассмотренный пример на любой систематический групповой блоковый (n,k)-код можно записать для него образующую матрицу

Единичная матрица является образующей для равномерного примитивного кода, поскольку с ее помощью могут быть построены все 2k-1 ненулевых комбинаций этого кода путем суммирования по модулю два ее строк в различных сочетаниях.

Дополняющая матрица, если не заданы проверочные уравнения, может быть получена путем подбора k различных комбинаций, содержащих n-k разрядов. Эти комбинации должны удовлетворять следующим условиям :

1) количество единиц в комбинации должно быть не менее d-1,

2) сумма по модулю два любых двух комбинаций должна содержать не менее d-2 единиц.

Решение. Начать построение целесообразно с нахождения дополняющей матрицы в данном случае n=7, k=4, n-k=3, т. D3,4. Следовательно, надо подобрать трехразрядные комбинации, каждая из которых содержит по d-1=3-1=2 единицы. Поскольку таких комбинаций всего три, а их требуется k=4, то в качестве четвертой выберем, не нарушая первого условия, комбинацию, содержащую три единицы. Тогда дополняющая матрица

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

и образующая матрица

из которой может быть найдена система проверочных уравнений

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

В качестве еще одной равноправной формы описания систематического (n,k)-кода служит т. проверочная матрица, обозначаемая обычно Hn,n-k. При построении проверочной матрицы к единичной квадратной матрице Jn-k слева приписывают матрицу, содержащую k столбцов и n-k строк, причем каждая ее строка формируется из соответствующего столбца дополняющей матрицы, т. приписываемая матрица представляет собой транспонированную дополняющую матрицу

Пример. Для кода из примера 3. 3- построить проверочную матрицу.

Проверочная матрица позволяет выбрать алгоритм кодирования и декодирования, исходя из того, что единицы в каждой ее строке соответствуют тем символам кодовой комбинации, сумма которых по модулю два должна быть равна 0. Так, из матрицы (3. 18) можно получить следующие уравнения проверок:

Естественно, что (3. 16) и (3. 19) полностью совпадают с той лишь разницей, что операции по (3. 16) выполняются при кодировании для получения значений контрольных разрядов в каждой кодовой комбинации, а операции по (3. 19) выполняются при декодировании для обнаружения и исправления ошибок.

Из анализа (3. 19) видно, что a1 входит во все три уравнения, а2 – в первое и второе, а3 – в первое и третье, а4 – во второе и третье. Следовательно, искажение любого аi нарушит вполне определенные уравнения, т. сумма по модулю два в них будет равна не нулю, а единице. По тому, какие именно уравнения нарушены, можно определить, в каком разряде произошла ошибка, и восстановить его истинное значение.

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

При считается, что кодовая комбинация принята верно или произошла не обнаруживаемая ошибка. Если , считается, что комбинация принята неверно, т. имеет место обнаружение ошибки. Если (n,k)-код используется только для обнаружения ошибок, то в теории кодирования доказывается, что при любой вероятности ошибочного приема кодового символа р £ 1/2 найдется код, для которого вероятность необнаруженной ошибки будет меньше вполне определенного значения. Такие коды называются кодами равномерно обнаруживающими ошибки.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

При выполнении проверок на приеме в соответствии с системой (3. 19) получается

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

синдром R=110, нарушены 1 и 2 уравнения, в которые входит а2, следовательно, ошибка в разряде а2 и тогда исправляющий вектор Е=0010000, а исправленная кодовая комбинация

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Пользуясь этим примером, обратим внимание на третью стоку образующей матрицы (3. 15). В части этой строки, соответствующей единичной матрице, единица расположена на месте разряда, в котором произошла ошибка, а получившийся синдром R равен части этой же строки, входящей в дополняющую матрицу.

Обобщая, можно сказать, что при ошибке в разряде а4 синдром будет 011, при ошибке в разряде а3 – 101, при ошибке в разряде а1 – 111.

То же самое следует из проверочной матрицы этого кода (3. 18), где первый столбец – синдром при ошибке в разряде а4 и т.

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

Базовые понятия помехоустойчивого кодирования и декодирования

Кодированием и декодированием (в широком смысле) называют любое преобразование сообщения в сигнал и обратно, сигнала в сообщение, путем установления взаимного соответствия. Преобразование следует считать оптимальным, если в конечном итоге производительность источника и пропускная способность канала окажутся равными, т. возможности канала будут полностью использованы. Данное преобразование разбивается на два этапа:

  • модуляция-демодуляция, позволяющая осуществить переход от непрерывного сигнала радиоканала к дискретному;
  • кодирование-декодирование (в узком смысле), во время которого все операции выполняются над последовательностью символов.

В свою очередь, кодирование-декодирование делится на два противоположных по своим действиям действиям этапа:

  • устранение избыточности в принимаемом от источника сигнале (экономное кодирование);
  • внесение избыточности в передаваемый по каналу цифровой сигнал (помехоустойчивое или избыточное кодирование) для повышения достоверности передаваемой информации.

Экономное кодирование направлено на то, чтобы передаваемый дискретный сигнал имел максимальную энтропию, т. максимальное среднее количество инфорации на символ. Тогда для его передачи по радиоканалу с выбранным модемом потребуется минимальная полоса частот. Основное свойство дискретного сигнала, в котором полностью устранена избыточность, – равная вероятность и независимость их появления в последовательности. В этом случае среднее количество информации на символ равно.

Принцип построения помехоустойчивых кодов

При помехоустойчивом кодировании в поток передаваемых символов вводятся дополнительные (избыточные) символы для исправления возникающих на приемной стороне ошибок. Это требует увеличения скорости передачи по каналу, что при выбранном типе модема эквивалентно расширению полосы частот сигнала и уменьшению энергии посылки. Поэтому может возникнуть правомерный вопрос о целесообразности использования избыточного кодирования. На этот вопрос дает ответ теорема Шеннона о пропускной способности непрерывного канала связи, из которой следует, что пропускная способность непрерывного канала увеличивается с расширением его полосы, но при оптимальном (в широком смысле) кодировании. Поэтому следует ожидать повышения достоверности передачи при заданной скорости и отношении сигнал/шум в канале при внесении избыточности. Однако не существует оптимального кодека для сообщения, не фиксированного по длительности. Тем не менее, избыточное кодирование стало широко применяться в целях повышения качества передачи, преимущественно в последние десятилетия, когда проблема создания сложных вычислительных устройств в малых габаритах была практически решена. Рассмотрим принципы кодирования на примере двоичного канала. Допустим, что источник обладает максимальной производительностью. Тогда обязательным условием внесения избыточности является увеличение числа переданных посылок за единицу времени по сравнению с их числом, поступающим от источника. Тип кода определяет принцип, по которому вносятя избыточные символы. В простейшем случае, группе из k символов источника ставится в соответствие n символов, передаваемых по каналу. Такой код называется блочным и записывается условно как (n , k)-код. Возможно также использование непрерывных кодов, характеризующихся тем, что операции кодирования и декодирования производятся над непрерывной последовательностью символов без разбиения на блоки. Рассмотрим принципы помехоустойчивого кодирования на примере блочного двоичного кода. Если к символам источника добавляются избыточные символы, то код называют систематическим. Если группе информационных символов ставится в соответствие новая группа символов, передаваемая по каналу, в которой информационных символов в явном виде нет, то код называется неразделимым. Требуется построить такой кодек, чтобы при фиксированной избыточности:

Читайте также:  Телефон не является абонентом мегафона и не может управляться

где r — число проверочных символов для разделимого кода, достоверность передачи была бы максимальной.

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

Основные параметры помехоустойчивых кодов

Введем понятие кодового расстояния. Предварительно отметим, что для оценки отличия одной кодовой комбинации от другой можно использовать расстояние Хэмминга , определяемое числом разрядов, в которых одна кодовая комбинация отличается от другой. Для двоичного кода:

где и — k-е символы кодовых комбинаций соответственно.

Наименьшее расстояние Хэмминга для данного кода называется кодовым расстоянием. Далее будем его обозначать через d. При независимых ошибках в канале корректирующую способность кода удается выразить через кодовое расстояние. Пусть имеется код с d = 1. Учитывая, что искажение одного символа изменяет расстояние Хэмминга на одну единицу, при применении кода с d = 1
обнаруживаются не все одиночные ошибки. Для того чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, получаем, что для обнаружения всех ошибок кратности l требуется код с. Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, чем для их обнаружения. Если кратность исправляемых ошибок равна l, то кодовое расстояние должно удовлетворять условию. Очевидно, что кодовое расстояние между разрешенными комбинациями можно сделать тем больше, чем больше избыточность. Однако при этом уменьшается длительность посылок и возрастает вероятность ошибок при их приеме. Поэтому вводят понятие эффективности избыточного кодирования как отношение вероятностей ошибочного приема кодовой комбинации из к информационных символов при передаче их примитивным и избыточным кодами:

Если код примитивный, то ошибка возникает, когда хотя бы в одном символе при приеме произошла ошибка. Вероятность такого события равна:

где Рош. п — вероятность ошибки в приеме одного символа при передаче сообщения примитивным кодом.

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

P(n,k) = ош. и(1 – Pош

где Рош. п — вероятность ошибки в приеме одного символа при передаче избыточным кодом.

Различие в Рош. п и Рош. и определяется уменьшением длительности посылки при передаче избыточным кодом в n/k раз. Величины Рош. п и Рош. и могут быть найдены, если известен вид модуляции и демодуляции, отношение P0 / N0 и длительность посылок источника.

Оценочные соотношения для параметров помехоустойчивых кодов

Задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния при введении избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным. Задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, не решена. Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных n / k, которые часто используются для выяснения того, насколько построенный код близок к оптимальному. Можно показать, что если существует блочный линейный код (n, k), то для него справедливо неравенство:

Выражение (1) называется верхней границей Хэмминга. Граница Хэмминга (1) близка к оптимальной для кодов с большими значениями n / k. Для кодов с малыми значениями n / k более точной вляется верхняя граница Плоткина:

Можно также показать, что существует блочный линейный (n , к)-код с кодовым расстоянием d, для которого справедливо неравенство:

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

Линейное блочное кодирование

Линейным блочным (n,k) – кодом называется множество N последовательностей длины n над GF(q), называемых кодовыми словами, которое характеризуется тем, что сумма двух кодовых слов является кодовым словом, а произведение любого кодового слова на элемент поля также является кодовым словом. Таким образом, линейный (n, k)-код можно получить из к линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными.

Способы задания линейных кодов

Представим базисные кодовые комбинации в виде ()-матрицы:

В теории кодирования матрица G называется порождающей. Тогда процесс кодирования заключается в выполнении операции:

где А — вектор размерности k, соответствующий сообщению;
В — вектор размерности n, соответствующий кодовой комбинации.

Порождающая матрица (1) содержит всю необходимую для кодирования информацию. Она должна храниться в памяти кодирующего устройства. Для двоичного кода объем памяти равен двоичных символов. При табличном задании кода кодирующее устройство должно запоминать двоичных символов. Две порождающие матрицы, отличающиеся друг от друга только порядком расположения столбцов, задают коды, которые имеют одинаковые расстояния Хэмминга между соответстствующими кодовыми комбинациями, а следовательно, одинаковые корректирующие способности. Такие коды называются эквивалентными. В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие по одной единице среди информационных символов. При этом порождающую матрицу (1) удается записать в канонической форме:

где I — единичная ( )-подматрица;
Р — ()- подматрица проверочных символов, определяющая свойства кода.

Матрица задает систематический код. Можно показать, что для любого линейного кода существует эквивалентный систематический код. Линейный (n, k)- код может быть задан так называемой проверочной матрицей Н размерности (). При этом некоторая комбинация В принадлежит коду только в том случае, если вектор В ортогонален всем строкам матрицы H, т. если выполняется равенство:

где T – символ транспонирования матрицы.

Поскольку равенство справедливо для любой кодовой комбинации, то:

Если принятая кодовая комбинация совпадает с одной из разрешенных В (это имеет место тогда, когда либо ошибки в принятых символах отсутствуют, либо при действии помех одна разрешенная кодовая комбинация переходит в другую), то:

где S – вектор размерности (), называемый синдромом;
— вектор принятой кодовой комбинации.

В противном случае S не равно 0, причем вид синдрома зависит только от вектора ошибок е. Действительно:

где В — вектор, соответствующий передаваемой кодовой комбинации.

При S = 0 декодер принимает решение об отсутствии ошибок, а при S0 — о наличии ошибок. Число различных синдромов, соответствующих разным сочетаниям ошибок, равно. По конкретному виду синдрома можно (в пределах корректирующей способности кода) указать на ощибочные символы и исправить их.

Строение декодера линейного кода

Декодер линейного кода (рис. 1) состоит из k-разрядного сдвигающего регистра, (n — k) блоков сумматоров по модулю 2, схемы сравнения, анализатора ошибок и корректора. Регистр служит для запоминания информационных символов принятой кодовой последовательности, из которых в блоках сумматоров формируются проверочные символы. Анализатор ошибок по конкретному виду синдрома, получаемого в результате сравнения формируемых на приемной стороне и принятых проверочных символов, определяет места ошибочных символов. Исправление информационных символов проводится в корректоре.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Рис. Структурная схема декодера линейного кода

Заметим, что в общем случае,при декодировании линейного кода с исправлением ошибок, в памяти декодера должна храниться таблица соответствий между синдромами и векторами ошибок, содержащая строк. С приходом каждой кодовой комбинации декодер должен перебрать всю таблицу. При небольших значениях (n – k) эта операция не вызывает затруднений. Однако для высокоэффективных кодов длиной n, равной нескольким десяткам, разность (n — k) принимает такие значения, что перебор таблицы из строк оказывается практически невозможным. Например, для кода, имеющего кодовое расстояние d = 5, таблица состоит из строк. При заданных значениях n и k существует линейных кодов. Задача заключается в выборе наилучшего (с позиции того или иного критерия) кода. Следует заметить, что до сих пор общие методы синтеза оптимальных линейных кодов не разработаны.

Циклические коды

Циклические коды относятся к классу линейных. Поэтому для их построения достаточно знать порождающую матрицу. Несмотря на это, можно указать другой, более простой способ построения циклических кодов, основанный на представлении кодовых комбинаций многочленами b(х) вида:

где – символы кодовой комбинации.

Над данными многочленами можно проводить все алгебраические действия с учетом того, что сложение здесь осуществляется по модулю 2. Каждый циклический (n,k) – код характеризуется так называемым порождающим многочленом. Им может быть любой многочлен р(х) степени (n-k), который делит без остатка двучлен (). Циклические коды характеризуются тем, что многочлены b(х) кодовых комбинаций делятся без остатка на р(х). Поэтому процесс кодирования сводится к нахождению по известным многочленам а(х) и р(х) многочлена b(х), делящегося на р(х), где а(х) — многочлен степени (k—1), соответствующий информационной последовательности символов. Очевидно, что в качестве многочлена b(х) можно использовать произведение а(х) и р(х). Однако при этом код оказывается несистематическим, что затрудняет процесс декодирования. Поэтому на практике, в основном, применяется следующий метод нахождения многочлена b(х). Умножим многочлен а(х) на () и полученное произведение разделим на р(х). Пусть:

где m(х) — частное;
с(х) — остаток.

Поскольку операции суммирования и вычитания по модулю 2 совпадают, то выражение (9) перепишем в виде:

Из соотношения (10) следует, что многочлен делится нa р(х) и, следовательно, является искомым. Многочлен имеет следующую структуру: первые (n – k) членов низшего порядка равны нулю, а коэффициенты остальных совпадают с соответствующими коэффициентами информационного многочлена а(х). Многочлен с(х) имеет степень меньше (n – k). Таким образом, в найденном многочлене b(х) коэффициенты при х в степени (n – k) и выше совпадают с информационными символами, а коэффициенты при остальных членах, определяемые многочленом с(х), совпадают с проверочными символами. В соответствии с формулой процесс кодирования заключается в умножении многочлена а(х) на и нахождении остатка от деления на р(х) с последующим его сложением по модулю 2 с многочленом. Операции умножения и деления многочленов легко осуществляются линейными цепями на основе сдвигающих регистров. В качестве иллюстрации на рис. 2, а представлена схема умножения многочлена b(x) степени n = 6 на многочлен по модулю.

Читайте также:  Как устранить ошибку 403 в Google Play Market для Android

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Рис. Схемы умножения (а) и деления (б) многочленов (частный случай)

На рис. 2 видно,что после семи тактов в регистре записывается многочлен. При делении многочлена b(х) степени n = 6 на многочлен (рис. 2, б) после семи тактов в регистре оказывается записанным остаток от деления.

Устройство кодеров циклического кода

На основе приведенных схем умножения и деления многочленов строятся кодирующие устройства для циклических кодов. На рис. 3 в качестве примера приведена схема кодера для (7, 4) – кода с порождающим многочленом. В исходном состоянии ключи и находятся в положении 1. Информационные символы поступают одновременно на вход канала и на выход ячейки сдвигающего регистра (это соответствует умножению многочлена а(х) на ). В течение четырех тактов происходит деление многочлена на многочлен. В результате в регистре записывается остаток, представляющий собой проверочные символы. Ключи и перебрасываются в положение 2, и в течение трех последующих тактов содержащиеся в регистре символы поступают в канал.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Рис. Структурная схема кодера циклического кода с порождающим многочленом

Циклический код может быть задан проверочным многочленом h(x). Кодовая комбинация В принадлежит данному циклическому коду, если. Проверочный многочлен связан с порождающим соотношением.

Задание кода проверочным многочленом эквивалентно заданию кода системой проверочных уравнений. Характерной особенностью циклического кода является то, что все проверочные уравнения можно получить из одного путем циклического сдвига индексов символов, входящих в исходное уравнение. Например, для (7, 4) – кода с порождающим многочленом проверочный многочлен имеет вид. Проверочные уравнения получаются из условия (12):

Осуществив умножение и приравняв коэффициенты при нулю, получим следующие уравнения, разрешенные относительно проверочных символов:

В качестве примера на рис. 4 показана схема кодера циклического (7,4) – кода, задаваемого проверочным многочленом , или, что то же самое, проверочными соотношениями. В исходном состоянии ключ находится в положении 1. В течение четырех тактов импульсы поступают в регистр, после чего ключ переводится в положение 2. При этом обратная связь замыкается. Начиная с пятого такта, формируются проверочные символы в соответствии с соотношениями. После седьмого такта все проверочные символы оказываются сформированными, ключ вновь переключается в положение 1. Кодер готов к приему очередного сообщения. Символы кодовой комбинации поступают в канал, начиная с пятого такта.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Рис. Структурная схема кодера циклического кода с проверочным многочленом

Корректирующая способность кода зависит от порождающего многочлена р(х). Поэтому его выбор очень важен при построении циклического кода. Необходимо помнить, что степень порождающего многочлена должна быть равна числу проверочных символов. Кроме того, многочлен р(х) должен делить двучлен. Обнаружение ошибок при использовании таких кодов заключается в делении многочлена , соответствующего принятой комбинации , на р(х). Если остаток s(x) оказывается равным нулю, то считается, что ошибки нет, в противном случае фиксируется ошибка. Пусть необходимо построить код, обнаруживающий все одиночные ошибки. В этом случае многочлен ошибок имеет вид , где i = 0, 1,. , n – 1. Решение задачи заключается в нахождении такого многочлена р(х), чтобы многочлен е(х) не делился на р(х). Наиболее простым, удовлетворяющим этому требованию, является многочлен. Аналогично можно построить код, обнаруживающий ошибки большей кратности. Многочлен зависит только от многочлена ошибок е(х) и играет ту же роль, что и вектор-синдром. Поэтому ошибки можно исправить на основе таблицы соответствий между е(х) и s(x), хранящейся в памяти декодера, как и при линейных нециклических кодах. Однако свойство цикличности позволяет существенно упростить процедуру декодирования. Один из алгоритмов исправления ошибок основан на следующих свойствах синдрома циклического кода. Пусть имеется циклический код с кодовым расстоянием d, исправляющий все ошибки до кратности включительно. Тогда можно показать, что:

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

На рис. 5 представлена схема декодера для (7, 4)-кода с порождающим многочленом. Код имеет кодовое расстояние d=3, что позволяет ему исправлять все однократные ошибки.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Принятая кодовая комбинация одновременно поступает в буферный регистр сдвига, служащий для запоминания кодовой комбинации и ее циклического сдвига, а также на устройство деления на многочленах для вычисления синдрома. В исходном состоянии ключ находится в положении 1. После семи тактов буферный регистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром. Если вес синдрома больше единицы, то декодер начинает проводить циклические сдвиги комбинации в буферном регистре (при отсутствии новой комбинации на входе) и одновременно вычислять их синдромы в устройстве деления. Если на некотором i-м шаге вес синдрома окажется меньше двух, то ключ переходит в положение 2, обратные связи в регистре деления разрываются. При последующих тактах ошибки исправляются путем подачи содержимого регистра деления на вход сумматора по модулю 2, включенного в буферный регистр. После семи тактов работы декодера в автономном режиме исправленная комбинация в буферном регистре возвращается в исходное положение (информационные символы будут занимать старшие разряды). Существуют и другие, более универсальные алгоритмы декодирования.

Коды Хэмминга

К циклическим кодам относятся коды Хэмминга, которые являются одним из немногочисленных примеров совершенных кодов. Они имеют кодовое расстояние d= 3 и исправляют все одиночные ошибки. Длина кода выбирается из условия , которое имеет простой смысл: число различных ненулевых синдромов равно числу символов в кодовой последовательности. Так, существуют коды Хэмминга (), в частности, коды: (7, 4), (15, 11), (31, 26), (63, 57) и т. Заметим, что ранее использованный многочлен является порождающим для кода Хэмминга (7, 4).

Коды БЧХ

Среди циклических кодов широкое применение нашли коды Боуза— Чоудхури—Хоквингема (БЧХ). Можно показать, что для любых целых положительных чисел m и l< n/2 существует двоичный код БЧХ длины. с кодовым расстоянием d > 2l + 1, причем число проверочных символов. Для кодов БЧХ умеренной длины и ФМ при передаче символов можно добиться значительного выигрыша (4 дБ и более). Он достигается при скоростях (1/3 < k/n < 3/4). При очень высоких и очень низких скоростях выигрыш от кодирования существенно уменьшается.

Мажоритарные коды

Иногда целесообразно использовать коды с несколько худшей корректирующей способностью по сравнению с лучшими известными кодами, но простые в реализации. К ним относятся коды, допускающие мажоритарное декодирование. Оно основано на возможности для некоторых циклических кодов выразить каждый информационный символ с помощью Q различных линейных соотношений. Решение о значении символа принимается по мажоритарному принципу. Для исправления всех ошибок до кратности l включительно необходимо иметь (2l + 1) независимых соотношений. В некоторой области значений параметров мажоритарные коды имеют корректирующую способность, незначительно уступающую корректирующей способности кодов БЧХ. В то же время их реализация сравнительно проста. Проиллюстрируем принцип мажоритарного декодирования на примере (7, 3) – кода с проверочной матрицей.

Рассматриваемый код является циклическим с порождающим многочленом. Он имеет кодовое расстояние d — 4. Используя матрицу , можно записать следующие соотношения для символа :

С учетом в декодере имеется возможность четырьмя разными способами вычислить первый информационный символ:

где — принятая кодовая комбинация.

При отсутствии ошибок ,т. все проверочные соотношения дают один и тот же результат. При наличии одного ошибочного символа три проверочных соотношения дают правильное значение, а соотношение, в котором участвует ошибочный символ, дает неверный результат. Принимая решение по мажоритарному принципу, декодер выдает правильный символ b. Пусть ошибочно приняты два символа. Если они входят в различные проверочные соотношения, то два проверочных соотношения дадут значение 1, а два других — значение 0. В этом случае декодер выдает сигнал отказа от декодирования. Если оба искаженных символа входят в одно проверочное соотношение, то все четыре проверки дают один и тот же результат. Декодер выдает правильный символ b. Аналогично определяются остальные информационные символы. Проверочные соотношения для символов и получаются из циклической перестановкой:

Схема декодера (рис. 6) состоит из сдвигающего регистра, сумматоров по модулю 2 и мажоритарного элемента М. Простота ее обусловлена тем, что в данном случае каждый символ кодовой комбинации участвует в одном проверочном соотношении. Код, для которого выполняется это условие, называется кодом с разделенными проверками.

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Рис. Структурная схема декодера циклического мажоритарного (7,3) – кода

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

Итеративные коды

Простыми в реализации являются также итеративные и каскадные коды. Идея построения итеративных кодов заключается в следующем. Информационные символы записываются в виде таблицы из столбцов и строк. К каждой строке таблицы дописываются проверочных символов в соответствии с некоторым кодом. Затем к каждому из столбцов полученной таблицы добавляют проверочных символов в соответствии с некоторым кодом (n_2, k_2). Таким образом строится код длиной с числом информационных символов. Можно показать, что для полученного двумерного итеративного кода кодовое расстояние d равно , где — кодовые расстояния для кодов соответственно. Кодовая комбинация двумерного итеративного кода обычно передается последовательно по строкам, начиная с первой. Соответственно, декодирование ведется сначала по строкам, а затем, после приема всего двумерного блока, — по столбцам. Проиллюстрируем построение кодовой комбинации двумерного итеративного кода. Пусть информационные символы записаны в виде таблицы:

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

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

Каскадные коды

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

Если существует проблема с определением кратности t ошибок, как следует распределить кодовое расстояние между двумя различными CPS

Рис. Cхема каскадного кодирования

Множество () информационных символов (в дальнейшем предполагается, что они двоичные) разбивается на подблоков по символов. Каждый подблок из символов рассматривается, как символ из алфавита объемом. Затем подблоков кодируются кодовыми комбинациями внешнего кода (рис. 7), составленными из подблоков по двоичному символу. Наконец, каждый из подблоков кодируется кодовыми комбинациями внутреннего -кода. Полученное множество кодовых слов внутреннего -кода является кодовым словом каскадного ()-кода. Обычно в качестве внешнего используют код Рида—Соломона с основанием , обеспечивающий максимальное кодовое расстояние при заданных , а в качестве внутреннего — двоичный -код.

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *