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

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

3.2. БЛОКОВЫЕ КОДЫ

Бинарные блоковые коды чаще всего рассматриваются в предположении, что источник безызбыточный, формирующий k-битовые блоки À = (à1,à2 ,..., àk ) двоичных символов ài = 0,1 с равной вероятностью

1Ì , где М = 2k , а для передачи используется двоичный симметричный канал

(ДСК) без памяти, наблюдением на выходе которого является вектор Y = (y1, y2 ,..., yn )= C + E , где Ñ = (ñ1,ñ2 ,...,ñn ) – кодовый вектор (кодовое слово), а Å = (å1,å2 ,...,ån ) – вектор ошибок с независимыми компонентами. При этом

элементы yi , si , åi – упомянутых векторов принимают двоичные значения 0 и

1, а символ «+» всюду в этом разделе обозначает поэлементное суммирование по модулю два. В ДСК вероятность появлении конкретного вектора ошибки Å убывает при увеличении кратности ошибки t (т.е. числа 1 в векторе Å , или, что равносильно, числа искаженных символов в переданном кодовом векторе). Поэтому оптимальной (максимально правдоподобной) стратегией декодирования оказывается правило минимального расстояния Хэмминга, согласно которому принятый вектор Y должен декодироваться в ближайший к нему, по Хэммингу, кодовый вектор C . Напомним, что в двоичном случае расстояние Хэмминга между Y и С есть просто число единиц среди элементов вектора Y + C .

Под термином код понимается множество из М кодовых слов. Отметим, что для произвольного кода с большим числом слов реализация оптимального правила декодирования может оказаться чрезвычайно затратной в аппаратнопрограммном отношении. Из-за существования довольно простых алгоритмов декодирования наибольшее применение находят линейные коды, являющиеся линейными подпространствами. В системах мобильной связи, в частности, нашли применение линейные коды Хэмминга, БЧХ, Голея, Рида-Маллера, Рида-Соломона (PC).

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

36

a1, a3, a6 ,bi

информационными, в то время как оставшиеся n-k позиций принадлежат избыточным символам, создаваемым кодером. Корректирующая способность оценивается с помощью кодового расстояния d0 – минимального расстояния Хэмминга между всевозможными парами кодовых слов. Чем больше d0, тем выше помехоустойчивость кода, а именно максимальное число (кратность) символьных ошибок, гарантированно обнаруживаемых кодом tî áí = d0 −1. Если же код используется для исправления ошибок, то это с гарантией выполнимо, если их кратность не превосходит tèñï ð = (d0 −1)/ 2 , где . – целая часть числа.

В случае, кода код должен исправлять какое-то количество ошибок tèñï ð и сверх этого обнаруживать tî áí > tèñï ð ошибок, его расстояние должно быть не

меньшим d0 = tî áí +tèñï ð +1.

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

Каждый проверочный бит bi , есть линейная комбинация некоторых вполне определенных информационных, например, bi = a1 +a3 +a6 . Благодаря свойствам сложения по модулю 2 последовательность содержит

четное число символов 1. Поэтому проверочные символы часто называют битами контроля четности или просто битами четности.

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

слов (базис кода) Ñbi , i =1, 2,...k , и проверочной матрицей	Н, обладающей
свойством
ÑÍ T = 0	(3.2)

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

Пример 3.1. Порождающая матрица кода Рида-Маллера (8,4) первого порядка имеет вид

	Cb1		1	1	1	1	1	1	1	1
G =	Cb2	=	0	0	0	0	1	1	1	1	.
	C		0	0	1	1	0	0	1	1
	b3
	Cb4		0	1	0	1	0	1	0	1

Кодовое слово есть линейная комбинация базисных векторов

Ñ = AG = a1Cb1 +a2Cb2 +a3Cb3 +a4Cb4 ,

37

k' > k k' −k

где A = (a1, a2 , a3, a4 ) информационные биты. Так, если A = 0110 ,	то
Ñ = 00111100 , при A =1110 – Ñ =11000011. Коды Рида-Миллера первого порядка
существуют для любых длин n = 2k −1 и имеют минимальное расстояние d0	=
n/2.
Отметим связь кодов Рида-Миллера с широко распространенными в

цифровой связи функциями Уолша. При замене двоичных символов 0 и 1 на +1 и -1 соответственно операция сложения по модулю 2 перейдет в умножение действительных чисел + 1 и -1. При таком отображении базисные векторы кода дадут функции Радемахера (меандры, период каждого из которых равен половине периода предыдущего), а остальные кодовые слова – прямые и противоположные функции Уолша, равные различным произведениям функций Радемахера (так называемые биортогональные сигналы). Функции Уолша (ортогональные коды) применяются в системе стандарта IS-95, а также в системах третьего поколения.

Проиллюстрируем теперь роль проверочной матрицы в построении линейного кода.

Пример 3.2. Пусть проверочная матрица кода Хэмминга (7,4) с расстоянием d0 = 3 , столбцами которой являются все 7 ненулевых 3-разрядных двоичных векторов, имеет вид

H =	1	0	1	1	1	0	0
	1	1	0	1	0	1	0	.
	0	1	1	1	0	0	1

Если кодовое слово Ñ = (a1, a2 , a3, a4 ,b1,b2 ,b3 ) подставить в (3.2) и выполнить матричное умножение, то получим соотношения для вычисления контрольных бит по информационным: b1 = a1 +a3 +a4 , b2 = a1 +a2 +a4 ,

b3 = a2 +a3 +a4.

В системах связи весьма распространены циклические коды, составляющие подкласс линейных, для которых разработаны эффективные процедуры декодирования. Они задаются с помощью порождающего многочлена g(x) степени n − k . При этом каждому кодовому слову формально сопоставляется многочлен с коэффициентами, равными элементам кодового вектора. Так, кодовому слову Ñ = (ñ1,ñ2 ,...,ñn ) соответствует многочлен

ñ(x) = ñ1xn−1 +ñ2 xn−2 +...+ñn , делящийся без остатка на порождающий g(x) , т.е. ñ(x) = f (x)g(x) , где f (x) – произвольный многочлен. Порождающие многочлены хороших циклических кодов, в том числе БЧХ и PC (являющихся подклассом недвоичных кодов БЧХ), табулированы в литературе.

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

38

по каналу), поскольку декодер знает, что они нулевые. Полученный (n-k' + k,k) линейный код, не являясь, строго говоря, циклическим, тем не менее, может быть декодирован теми же способами, что и исходный. Минимальное расстояние укороченного циклического кода, разумеется, не меньше расстояния исходного кода, чем и объясняется широкое использование приема укорочения на практике.

Слова циклического кода с любым заданным порождающим многочленом можно переупорядочить, преобразовав код в систематический. Для этого информационная последовательность А (многочлен a(x) )

сдвигается влево на	n-k позиций:	a1, a2 ,..., ak ,0,0,...,0 ,	что соответствует
умножению a(x) на	X n−k . Далее	вычисляется остаток	b(x) от деления
полученного многочлена a(x)X n−k на g(x) , т.е.
	b(x) = a(x)X n−k mod g(x).		(3.3)

Степень полученного остатка b(x) не превышает n-k, т.е. степени порождающего многочлена g(x) . Вычитание (равносильное для кодов над полями характеристики 2 прибавлению) остатка из многочлена a(x)X n−k дает требуемый кодовый многочлен ñ(x) = a(x)X n−k +b(x) .

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

Для обнаружения ошибок декодер проверяет принадлежность принятой последовательности Y данному коду (подпространству): если Y является кодовым словом, то принимается решение об отсутствии ошибок, в противном случае фиксируется наличие ошибки. Для этого вычисляется синдром

S =YÍ T = (C + E)H T = EÍ T ,

(3.4)

который с учетом (3.2) не зависит от кодового слова и определяется только вектором ошибки Е.

Если S = 0 , то Y является одним из М кодовых слов и, следовательно, максимально правдоподобная оценка вектора ошибки Å = 0 . Решение об отсутствии ошибок будет правильным, если в действительности E = 0 . Но согласно (3.2) синдром S = 0 и в случаях, когда Е совпадает с любым ненулевым кодовым словом. Такие ошибки не будут обнаружены. Их общее количество составляет 2k −1 . Для кода примера 3.2, в частности, трехкратные ошибки Е=1110000 и Е=0011010 дают нулевой синдром и не обнаруживаются.

Если S ≠ 0 , то принимается всегда правильное решение Å ≠ 0 .

Для обнаружения ошибок рекомендуется использовать протокол контроля циклическим избыточным кодом – ЦИК (в зарубежных источниках CRC - cyclic redundancy code). Для информационной последовательности А произвольной длины k по (7.3) вычисляется остаток b(x) , который передается

39

вместе с А. На приемной стороне по А' снова вычисляется остаток b(x) , который сравнивается с принятым b' (x) , т.е. фактически определяется синдром. При их равенстве выносится решение об отсутствии ошибок, в

противном случае	–	о наличии. Доля пропущенных ошибок –
(2k −1) (2k+m −1)≈1 2m	–	зависит только от степени т многочлена g(x) .

Например, в транкинговых системах TETRA используются многочлены с

m = 7 и m =16 .

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

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

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

слова пространство принятых последовательностей Y разбивается на 2n−k смежных классов, каждый из которых характеризуется тем, что разности любых входящих в него векторов являются кодовыми словами. Для каждого класса заранее определяется максимально правдоподобный вектор ошибок El , (лидер), сдвигающий любое кодовое слово в данный смежный класс. Задача декодера состоит в определении номера смежного класса (синдрома), в который попадает принятый вектор Y. По синдрому определяется (считывается из памяти декодера) лидер El . Каждому ненулевому синдрому может быть сопоставлен некоторый лидер. В результате максимальное число исправляемых ошибок равно 2n−k −1. Схематично процесс декодирования показан на рис. 3.2.

Если реальная ошибка, имевшая место в канале, совпадает с лидером Å = El , она будет исправлена.

При больших n-k наиболее сложной операцией является сопоставление синдрому вектора El /

Как следует из (3.4), для однократных ошибок синдром равен транспонированному столбцу проверочной матрицы с номером, равным

40

номеру искаженного бита. Поэтому для исправления всех однократных ошибок требуется, чтобы столбцы проверочной матрицы были ненулевыми и не повторялись. Матрица из примера 3.2 обладает этим свойством, и любая из 7 возможных однократных ошибок данным кодом исправляется. Действительно, если E = 00110000 , то S =101, которому в декодере заранее составлен лидер El = 0010000 , совпадающий с фактическим вектором ошибки.

Y S = YHТ Еl C = Y +El

3.2.Схема синдромного декодирования линейного кода

Однако указанный синдром может появиться и при возникновении двукратной ошибки, например, при Е=1100000 или Е=0001010. Декодер, действуя по схеме на рис. 7.4, по-прежнему добавит к принятой последовательности El = 0010000 , так что в результате ошибка не только не

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

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

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

Для декодирования кодов БЧХ, один из недвоичных подклассов которых составляют PC коды, разработаны квазиоптимальные алгебраические алгоритмы, которые, уступая алгоритму максимального правдоподобия, тем не менее, обеспечивают исправление ошибок в пределах, гарантируемых кодовым расстоянием. В основе их лежит не векторное описание ошибок, которое, как показывают рассмотренные примеры, обладает избыточностью за счет многих нулей, а просто указание номеров позиций, в которых произошло искажение символа. Так, для задания в примере 3.2 двукратных ошибок Е = 1100000 или Е = 0001010 проще сказать, что в первом случае искажены биты на 1-й и 2-й позициях, а во втором – на 4-й и 6-й.

В алгебраических алгоритмах позициям кодовых символов сопоставляются степени примитивного элемента а расширенного конечного поля GF(q), где q = 2т= п+1 (натуральное т называется степенью расширения поля). Для примера 7.2 последовательность номеров позиций отображается в степени а как à0 =1, à1, à2 , à3, à4 , à5 , à6 , где à – примитивный элемент поля GF(23). Тогда вышеуказанные двукратные ошибки описываются так: искажены биты на позициях à0 , à1 и à3, à5 . Степени à , отвечающие позициям, содержащим ошибки, называются локаторами ошибок.

41