Факультет информатики. Локальные и глобальные сети Локальные и глобальные сети

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

Коды Хэмминга. Кодом Хэмминга называется (n, k) код, который задается матрицей проверок H(n, k), имеющей r=nk строк и 2r1 столбцов, причем столбцами H(n, k) являются все различные ненулевые двоичные последовательности длины г (rразрядные двоичные числа от 1 до 2r1).

Пример. Построим на основе (7,4)кода Хэмминга код (8,4). Проверочная матрица такого кода имеет вид: 1 1 1 1 0 0 0 0 H(8,4) = 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1.

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

Практические примеры циклических кодов. Простой (n, n 1)код с проверкой на четность. Покажем, что (n, n 1)код является циклическим кодом с q(x)=1+х. Действительно, проверочный многочлен имеет вид:

Укороченные циклические коды. Циклические (n, k)коды как и любые групповые коды, могут укорачиваться с формированием (ni, ki)кода.

Коды Хэмминга. При изучении групповых кодов уже давалось определение кодов Хэмминга по виду проверочной матрицы. Можно показать, что коды Хэмминга обладают всеми свойствами циклических кодов и являются частным случаем кодов БЧХ с минимальным расстоянием dmin=3 или dmin=4.

Принципы построения каскадных кодов.

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

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

Поступающие от источника сообщений данные разбиваются на блоки из К недвоичных (mичных) символов, содержащие k информационных элементов (k=К*m), которые кодируются недвоичным (N, К)кодом. Очевидно, что каждый коэффициент (N, К)кода (сi и bi) содержит m двоичных элементов. Последовательность (N, К)кода, состоящая из n1 = N*m двоичных элементов поступает на внутренний кодер, где разбивается на mэлементные блоки, которые кодируются внутренним (n2, m) кодом. Число кодовых комбинаций N=K+R, поэтому на выходе внутреннего кодера число двоичных элементов будет n = n2*N.

Таким образом, в канал связи передается последовательность комбинаций (n2, m)кода, образующих в совокупности комбинации каскадного (N, К)кода. Каскадный принцип кодирования объединяет алгебраический и вероятностный подходы, позволяя получить очень длинные коды, для которых при возрастании длины блока вероятность ошибки в каналах без памяти уменьшается по экспоненте, а сложность декодера возрастает лишь как небольшая степень длины блока.

Блок длины n передается по каналу и поступает во внутренний декодер, где осуществляется повышение достоверности за счет (n2, m)кода.

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

Процедуру каскадного кодирования можно уяснить на рис. 19.18.

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

В теории кодирования доказано, что каскадный код является линейным и его кодовое расстояние Dk нe меньше, чем произведение кодовых расстояний внешнего (D) и внутреннего (d) кодов: Dk = D*d.

Остальные параметры двоичного кода также легко определяются по значению параметров внешнего и внутреннего кодов: n = N*n2, k = К*m, r = n k = N*n2 К*m.

Каскадный код lго порядка использует систему l внутренних вложенных кодов и 1 внешних кодов. Вложенным называется код, множество слов которого является подмножеством кодовых слов другого кода.

Преимущества каскадных кодов.

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

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

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

На практике в качестве внешнего кода часто используют qичный (q = 2m 1) циклический код РидаСоломона, а в качестве внутреннего кода –

(n2, m) код БЧХ.


На главную