6.1. Кодирование сигнала и структурированные последовательности
6.1.1. Антиподные и ортогональные сигналы
6.1.2. М-арная передача сигналов
6.3. Структурированные последовательности
6.3.1.1. Дискретный канал без памяти
6.3.2. Степень кодирования и избыточность
6.3.3. Коды с контролем четности
6.3.4. Зачем используется кодирование с коррекцией ошибок
6.3.4.1. Компромисс 1: достоверность илиполоса пропускания
6.3.4.2. Компромисс 2: мощность или полоса пропускания
6.3.4.3. Эффективность кодирования
6.3.4.4. Компромисс 3: скорость передачи данных или полоса пропускания
6.3.4.5. Компромисс 4: пропускная способность или ширина полосы пропускания
6.4.2. Векторные подпространства
6.4.3. Пример линейного блочного кода (6, 3)
6.4.5. Систематические линейные блочные коды
6.4.7. Контроль с помощью синдромов
6.4.8.1. Синдром класса смежности
6.4.8.2. Декодирование с исправлением ошибок
6.5. Возможность обнаружения и исправления ошибок
6.5.1. Весовой коэффициент двоичных векторов и расстояние между ними
6.5.2. Минимальное расстояние для линейного кода
6.5.3. Обнаружение и исправление ошибок
6.6. Полезность нормальной матрицы
6.6.1. Оценка возможностей кода
6.7.1. Алгебраическая структура циклических кодов
6.7.2. Свойства двоичного циклического кода
6.7.3. Кодирование в систематической форме
6.7.4. Логическая схема для реализации полиномиального деления
6.7.5. Систематическое кодирование с (n-k)-разрядным регистром сдвига
6.7.6. Обнаружение ошибок с помощью (n-k)-разрядного регистра сдвига
6.1. Кодирование сигнала и структурированные последовательности
Тему канального кодирования можно условно разделить на два раздела: кодирование (или обработка) сигнала и структурированные последовательности (или структурированная избыточность), как это показано на рис. 6.1. Кодирование сигнала означает преобразование сигнала в некий «улучшенный сигнал», позволяющий сделать процесс, обнаружения менее подверженным ошибкам. Метод структурированных последовательностей — это преобразование последовательности данных в новую, «улучшенную последовательность», обладающую структурной избыточностью (которая вмешает избыточные биты). Эти избыточные разряды служат для определения и исправления ошибок. На выходе процедуры кодирования получается закодированный (формой сигнала или структурированной последовательностью) сигнал, имеющий лучшие пространственные характеристики, чем некодированный. Итак, сначала рассмотрим некоторые методы кодирования сигнала, а затем, начиная с раздела 6.3, обсудим суть структурированных последовательностей.
6.1.1. Антиподные и ортогональные сигналы
Антиподные и ортогональные сигналы уже обсуждались ранее, поэтому мы лишь напомним их основные особенности. В примере, приведенном на рис. 6.2, показано аналитическое представление набора синусоидальных антиподных сигналов (
), а также его векторное и графическое представление. Какие существуют альтернативные определения антиподных сигналов? О таких сигналах можно сказать, что они либо являются зеркальными отображениями друг друга, либо один сигнал является отрицательным по отношению к другому, либо они различаются между собой на 180°.
Рис. 6.2. Пример антиподного набора сигналов
В примере, приведенном рис. 6.3, показан набор ортогональных сигналов, которые имеют вид импульсов описывающихся следующими выражениями.
Рис. 6.3. Пример двоичного набора ортогональных сигналов
В данном случае p(t) — импульс длительностью 
, где Т— период. В системах связи .возможны и другое наборы ортогональных сигналов, например часто используемые sin x и cos x Любой набор равноэнергетических сигналов si(t), i = l,2,…,M, будет ортонормированным (ортогональным и нормированным на 1),тогда и только тогда, когда
(6.1)
где zij является коэффициентом взаимной корреляции (cross-correlation coefficient), а величина Е — энергией сигнала, выражаемой следующим образом.
(6.2)
Из графического представления на рис. 6.3 видно, что s1(t) и s2(t) не могут взаимодействовать, поскольку они разнесены во времени. Векторное представление показывает, что ортогональные сигналы перпендикулярны. Посмотрим на другие, альтернативные определения ортогональных сигналов или, векторов. Можно сказать, например, что скалярное произведение двух разных векторов в ортогональном наборе должно быть равно нулю. В двух- и трехмерных декартовых системах координат векторы сигналов можно представить геометрически, как взаимно ортогональные друг к другу. Можно также сказать, что один вектор имеет нулевую проекцию на другой или один сигнал не может взаимодействовать с другим, поскольку они»не принадлежат одному и тому же пространству сигналов.
6.1.2. M-арная передача сигналов
При M-арной передаче сигналов процессор за один такт работы принимает k бит данных. После этого он указывает модулятору произвести один из M = 2k сигналов; частным случаем k = 1 является двоичная передача сигнала. Для k > 1 М-арную передачу сигналов можно рассматривать как процедуру кодирования формы сигнала. При ортогональной передаче сигналов (например, сигналов MFSK) увеличение k приводит к повышению достоверности передачи или уменьшению требуемого Eb/NQ за счет увеличения полосы пропускания; при неортогональной передаче сигналов (например, сигналов MPSK) улучшение эффективности использования полосы пропускания происходит за счет снижения достоверности передачи или возрастания требуемого Eb/NQ. Подходящий выбор формы сигнала позволяет найти компромисс между вероятностью ошибки, Eb/NQ и эффективностью использования полосы пропускания. Более подробно такие компромиссы рассмотрены в главе 9.
6.1.3. Кодирование сигнала
Процедура кодирования сигнала состоит в преобразовании набора сигналов (представляющих набор сообщений) в усовершенствованный набор сигналов. Этот улучшенный набор можно использовать для получения более приемлемой величины РВ, соответствующей исходному набору. Наиболее популярные из таких кодов сигнала называются ортогональными (orthogonal) и биортогональными кодами (biorthogonal). В процессе кодирования каждый сигнал набора пытаются сделать настолько непохожим на другие, насколько это возможно, чтобы для всех пар сигналов коэффициент взаимной корреляции zij (см. уравнение 6.1) имел наименьшее возможное значение. Строго это условие выполняется тогда, когда сигналы антикоррелируют (zij = -1); этого можно добиться только в том случае, если в наборе всего два значения (М =2) и они антиподны друг другу. Вообще, все коэффициенты взаимной корреляции можно сделать равными нулю [1]. В этом случае набор будет ортогональным. Наборы антиподных сигналов являются оптимальными в том смысле, что все сигналы максимально удалены друг от друга, как можно видеть на рис. 6.2. Расстояние d между векторами сигналов определяется как 
, где Е— энергий сигнала на интервале T, как показано а уравнении (6.2). Сравнив пространственные характеристики ортогональных сигналов с характеристиками антиподных сигналов, приходим к выводу, что о первых можно сказать нечто вроде «довольно хорошо» (при данном уровне энергии сигнала). На рис. 6.3 расстояние между векторами ортогональных сигналов составляет 
Взаимная корреляция между двумя сигналами является мерой расстояния между двумя векторами сигналов. Чем меньше взаимная корреляция, тем больше векторы удалены друг от друга. Это можно проверить с помощью рис. 6.2, где антиподные сигналы (для которых zij =-l) представлены векторами, наиболее удаленными друг от друга, и рис. 6.3, где ортогональные сигналы (для которых zij = 0) представлены векторами, расположенными ближе друг к другу, чем антиподные векторы. Очевидно, что расстояние между идентичными сигналами (zij = 1) должно быть равно нулю.
Условие ортогональности в уравнении 6.1 записано через сигналы si(t) и sj(t), где i,j = 1, 2, …,М (М — количество сигналов в наборе). Каждый сигнал набора 
может содержать последовательность импульсов с уровнями +1 или -1, которые представляют двоичную 1 или 0. Если выразить набор в таком виде, уравнение (6.1) можно упростить, положив, что состоит из ортогональных сигналов тогда и только тогда, когда
(6.3)
6.1.3.1. Ортогональные коды
Набор однобитовых данных можно преобразовать с помощью ортогональных кодовых слов, состоящих из двух разрядов каждое, которые описываются строками показанной ниже матрицы Н1.
Набор данных Набор ортогональных кодовых слов
(6.4,а)
В этом и следующих примерах проверка ортогональности набора кодовых слов производится с помощью уравнения (6.3). Для кодирования набора двухбитовых данных упомянутый выше набор следует расширить по горизонтали и вертикали, что дает матрицу Н2.
Набор данных Набор ортогональных кодовых слов
(6.4,б)
Правый нижний квадрант является дополнением к исходному набору кодовых слов. С помощью подобной процедуры можно определить и ортогональный набор Н3для набора 3-битовых данных.
Набор данных Набор ортогональных кодовых слов
(6.4,в)
Вообще, для набора k-битовых данных из матрицы Hk-1, можно построить набор кодовых слов Hk размерностью 2k х 2k, который называется матрицей Адамара (Hadamard matrix).
(6.4,г)
Каждая пара слов в каждом наборе кодовых слов H1, H2, H3, …, Hk, … содержит одинаковое количество совпадающих и несовпадающих разрядов [2]. Поэтому, в соответствии с уравнением (6.3), zij = 0 (при 
) и каждый из этих наборов ортогонален.
Точно так же, как М-арная передача сигналов с ортогональной модуляцией (такой, как MFSK) понижает РB, кодирование информации ортогональным набором сигналов при когерентном обнаружении дает абсолютно такой же результат. Для одинаковых, равноэнергетических ортогональных сигналов вероятность ошибки в кодовом слове (символе), РЕ, можно оценить сверху, как [2]
, (6.5)
где размер набора кодовых слов М равен 2k, a k — это число информационных бит в кодовом слове. Функция Q(x) определена в уравнении (3.43), Es=kEb является энергией кодового слова. При фиксированном М с ростом Eb/N0 оценка становится все более точной; уже для РE(М)
10-3 уравнение (6.5) является довольно хорошим приближением. Для выражения вероятности появления ошибочного бита мы будем использовать связь между рв и РЕ, которая дается уравнением (4.112). Приведем ее повторно.
(6.6)
В результате объединения уравнений (6.5) и (6.6) вероятность появления ошибочного бита можно оценить следующим образом.
(6.7)
6.1.3.2. Биортогональные коды
Биортогональный набор сигналов, состоящий из М сигналов или кодовых слов, получается из ортогонального набора, состоящего из M/2 сигналов, путем дополнения последнего сопряженными значениями каждого сигнала.
Например, набор 3-битовых данных можно преобразовать в биортогональный набор кодовых слов следующим образом.
Набор данных Набор ортогональных кодовых слов
В действительности биортогональный набор состоит из двух ортогональных кодов, таких, что для каждого кодового слова в одном наборе имеется ‘антиподное ему слово в другом. Биортогональный набор состоит из комбинации ортогональных и антиподных сигналов. Если использовать коэффициенты zij, введенные в уравнении (6.1), то биортогональные коды можно представить следующим образом.
(6.8)
Одно из преимуществ биортогональных кодов перед ортогональными заключается в том, что при передаче аналогичной информации размер кодового слова биортогональных кодов вдвое меньше размера кодового слова ортогональных кодов (сравните строки матрицы В3со строками представленной ранее матрицы Н3). Следовательно, при использовании биортогональных кодов требования к полосе пропускания вдвое слабее, чем при использовании ортогональных кодов. Поскольку антиподные векторы сигналов имеют лучшие пространственные характеристики, чем ортогональные, не должно удивлять, что биортогональные коды лучше ортогональных. Для одинаковых, равноэнергетических биортогональных сигналов вероятность ошибки в кодовом слове (символе) можно оценить [2] следующим образом.
(6.9)
При фиксированном М с ростом En/N0 оценка становится все более точной. Зависимость РB(М) от PE(м) является довольно сложной, но ее, согласно [2], можно аппроксимировать следующим образом.
Это приближение становится достаточно хорошим при M>8. Таким образом, Можно записать следующее.
(6.10)
Описанные биортогональные коды значительно снижают РB по сравнению с ортогональными кодами и требуют только вдвое меньшей полосы пропускания, чем аналогичные ортогональные коды.
6.1.3.3. Трансортогональные (симплексные) коды
Код, получаемый из ортогонального путем удаления первого разряда каждого кодового слова, называется трансортогональным (transorthogonal), или симплексным (simplex) кодом. Такой код описывается следующими значениями zij.
(6.11)
С точки зрения минимальной энергии, необходимой для поддержания заданной вероятности ошибки, симплексный код эквивалентен равновероятному ортогональному набору. Сравнивая достоверность передачи ортогонального, биортогонального и симплексного кодов, можно сказать, что симплексный код имеет наименьшее требуемое Eb/N0 для получения определенной частоты появления символьных ошибок. Впрочем, при больших М все три схемы очень похожи между собой в смысле достоверности передачи. При этом биортогональное кодирование, по сравнению с другими методами, требует лишь половины полосы пропускания. В то же время для каждого из этих кодов требования к полосе пропускания (и сложность системы) экспоненциально растут с увеличением М; так что подобные схемы кодирования годятся лишь тогда, когда доступна значительная полоса пропускания.
6.1.4. Примеры системы кодирования сигналов
На рис. 6.4 дается пример присвоения k-битовому сообщению из набора размером M = 2k кодированной последовательности импульсов из кодового набора аналогичного размера. Каждое из k-битовых сообщений выбирает один генератор, производящий кодированную последовательность или кодовое слово. Последовательности в кодированном наборе, заменяющие исходные сообщения, формируют набор сигналов с хорошими Пространственными характеристиками (например, ортогональный, биортогональный). Для ортогонального кода, описанного в разделе 6.1.3.1, каждое кодовое слово состоит из М = 2k импульсов (представляющих кодовые биты). Таким образом, 2k кодовых бит заменяют k информационных бит. Затем выбранная последовательность с использованием двоичной PSK модулируется несущей волной, так что фаза (φj = 0 или я) несущей волны в течение каждого интервала передачи кодированного бита, 
.соответствует амплитуде (j=-1 или 1) j-го биполярного импульса в кодовом слове. В приемнике, показанном на рис. 6.5, сигнал демодулируется и подается на М корреляторов (или согласованных фильтров). Для ортогональных кодов, таких как описаны в разделе 6.1.3.1 (которые определяются матрицей Ада-мара), за период передачи кодового слова (
) определяются корреляции принятого сигнала. Для систем связи реального времени сообщения не могут опаздывать, поэтому время передачи кодового слова должно совпадать е длительностью сообщения. Следовательно, T также можно выразить как 
, где Тb — длительность битов сообщения. Отметим, что длительность бита сообщения в M/k раз больше, чем у кодового бита. Другими словами, кодовые биты или кодированные импульсы (сигналы PSK) должны перемещаться со скоростью, в M/k раз большей, чем биты сообщения. Для ортогонально кодированных сигналов и каналов с шумом AWGN математическое ожидание выходной мощности для каждого коррелятора в момент времени Т равно нулю; исключением является только коррелятор, соответствующий переданному кодовому слову.
Рис. 6.4. Система кодирования сигналов (передатчик)
Рис. 6.5. Система кодирования сигналов с когерентным обнаружением (приемник)
Каковы преимущества описанного ортогонального кодирования сигналов по сравнению с обычным поступлением в каждую единицу времени одного бита или одного импульса? Можно оценить достоверность передачи с таким кодированием и без него, сравнив уравнение (4.79) для когерентного обнаружения антиподных сигналов с уравнением (6.7) для когерентного обнаружения ортогональных кодовых слов. При данном размере k-битового сообщения (скажем, k = 5) и желаемой вероятности появления ошибочного бита (например, 10-5), обнаружение ортогональных кодовых слов (каждое из которых состоит из 5 бит) может выполняться с приблизительно на 2,9 дБ меньшим отношением Eb/N0, чем побитовое обнаружение антиподных сигналов. (Проверить этот факт предоставляется читателю в качестве задачи 6.28.) Данный результат можно было предвидеть, сравнив рабочие характеристики ортогональной передачи сигналов на рис. 4.28 с характеристиками бинарной (антиподной) передачи на рис. 4.29. Чем мы платим за такой уровень достоверности передачи? Плата выражается в увеличении полосы пропускания. В приведенном примере передача некодированного сообщения — это посылка 5 бит. Сколько кодированных импульсов необходимо отправить для передачи с кодированием каждой последовательности сообщения? В данном примере каждая 5-битовая последовательность сообщения представлена М = 2k = 25 = 32 кодовыми битами или кодированными импульсами. 32 кодированных импульса, составляющих кодовое слово, нужно отправить за то же время, что и соответствующие исходные 5 бит. Таким образом, требуемая ширина полосы пропускания составляет 32/5 от ширины полосы пропускания в случае без кодирования. Вообще, полоса пропускания, необходимая для подобных ортогонально кодированных сигналов, в M/k раз больше требуемой в случае передачи без кодирования. Далее мы рассмотрим более выгодные и эффективные способы получения компромиссов между шириной полосы пропускания и схемой кодирования [3, 4].
6.2. Типы защиты от ошибок
Перед тем как начать обсуждение структурированной избыточности, рассмотрим два основных метода использования избыточности для защиты от ошибок. В первом методе, обнаружение ошибок и повторная передача, для проверки на наличие ошибки используется контрольный бит четности (дополнительный бит, присоединяемый к данным). При этом приемное оконечное устройство не предпринимает попыток исправить ошибку, оно просто посылает передатчику запрос на повторную передачу данных. Следует заметить, что для такого диалога между передатчиком и приемником необходима двухсторонняя связь. Второй метод, прямое исправление ошибок (forward error correction — FEC), требует лишь односторонней линии связи, поскольку в этом случае контрольный бит четности служит как для обнаружения, так и исправления ошибок. Далее мы увидим, что не все комбинации ошибок можно исправить, так что коды коррекции классифицируются в соответствии с их возможностями исправления ошибок.
6.2.1. Связность оконечных устройств
Оконечные устройства систем связи часто классифицируют согласно их связности с другими оконечными устройствами. Возможные типы соединения, показанные на рис. 6.6, называются симплексными (simplex) (не путайте с симплексными, или трансортогональными кодами), полудуплексными (half-duplex) и полнодуплексными (full-duplex). Симплексное соединение на рис. 6.6, а — это односторонняя линия связи.
Передача сигналов производится только от оконечного устройства А к оконечному устройству В. Полудуплексное соединение на рис. 6.6,б это линии связи, посредством которой можно осуществлять передачи сигналов в обоих направлениях, но не одновременно. И наконец, полнодуплексное соединение (рис. 6.6, в) — это двусторонняя связь, где передача сигналов происходит одновременно в обоих направлениях.
Передача только в одном направлении а)
а)
б)
в)
Рис. 6.6. Классификация связности оконечных устройств: а) симплексная; б) полудуплексная; в) полнодуплексная
6.2.2. Автоматический запрос повторной передачи
Если зашита от ошибок заключается только в их обнаружении, система связи должна обеспечить средства предупреждения передатчика об опасности, сообщающие, что была обнаружена ошибка и требуется повторная передача. Подобные процедуры защиты от ошибок известны как методы автоматического запроса повторной передачи (Automatic Repeat Request — ARQ). На рис. 6.7 показаны три наиболее распространенные процедуры ARQ. На каждой схеме ось времени направлена слева направо. Первая процедура ARQ, запрос ARQ с остановками (stop-and-wait ARQ), показана на рис. 6.7, а. Ее реализация требует только полудуплексного соединения, поскольку передатчик перед началом очередной передачи ожидает подтверждения об успешном приеме (acknowledgement — АСК) предыдущей. В примере, приведенном на рисунке, третий блок передаваемых данных принят с ошибкой. Следовательно, приемник передает отрицательное подтверждение приема (negative acknowledgment — NAK); передатчик повторяет передачу третьего блока сообщения и только после этого передает следующий по очередности блок. Вторая процедура ARQ, непрерывный запрос ARQ с возвратом (continuous ARQ with pullback), показана на рис. 6.7,б. Здесь требуется полно-дуплексное соединение. Оба оконечных устройства начинают передачу одновременно: передатчик отправляет информацию, а приемник передает подтверждение о приеме данных. Следует .отметить,„что каждому блоку передаваемых данных присваивается порядковый номер. Кроме того, номера кадров АСК и NAK должны быть согласованы; иначе говоря, задержка распространения сигнала должна быть известна априори, чтобы передатчик знал, к какому блоку сообщения относится данный кадр подтверждения приема. В примере на рис. 6,7,б время подобрано так, что между отправленным блоком сообщений и полученным подтверждением о приеме существует постоянный интервал в четыре блока. Например, после отправки сообщения 8, приводит сигнал NAK, сообщающий об ошибке в блоке 4. При использовании процедуры ARQ передатчик «возвращается» к сообщению с ошибкой и снова передает всю информацию, начиная с поврежденного сообщения. И наконец, третья процедура, именуемая непрерывным запросом ARQ с выборочным повторением (continuous ARQ with selective repeat), показана на рис. 6.7, в. Здесь, как и во второй процедуре, требуется полнодуплексное соединение. Впрочем, в этой процедуре повторно передается только искаженное сообщение; затем передатчик продолжает передачу с того места, где она прервалась, не выполняя повторной передачи правильно принятых сообщений.
а)
б)
в)
Рис. 6.7. Автоматический запрос повторной передачи (ARQ): а) запрос
ARQ с остановками (полудуплексная связь); б) непрерывный запрос ARQ с возвратом (полнодуплексная связь); в) непрерывный запрос ARQ с выборочным повторением (полнодуплексная связь)
Выбор конкретной процедуры ARQ является компромиссом между требованиями эффективности применения ресурсов связи и необходимостью полнодуплексной связи. Полудуплексная связь (рис. 6.7, а) требует меньших затрат, нежели полнодуплексная; в то же время она менее эффективна, что можно определить по количеству пустых временных интервалов. Более эффективная работа, показанная на рис. 6.7, б, требует более дорогой полнодуплексной связи.
Главное преимущество схем ARQ перед схемами прямого исправления ошибок (forward error correction — FEC) заключается в том, что «обнаружение ошибок требует более простого декодирующего оборудования и меньшей избыточности, чем коррекция ошибок. Кроме того, она гибче; информация передается повторно только при обнаружении ошибки. С другой стороны, метод FEC может оказаться более приемлемым (или дополняющим) по какой-либо из следующих причин.
1. Обратный канал недоступен или задержка при использовании ARQ слишком велика.
2. Алгоритм повторной передачи нельзя реализовать удобным образом.
3. При ожидаемом количестве ошибок потребуется слишком много повторных передач.
6.3. Структурированные последовательности
В разделе 4.8 мы рассмотрели цифровую передачу данных посредством M=2k сигналов (М-арная передача сигнала), где каждый сигнал содержит k бит информации. Было показано, что при ортогональной M-арной передаче сигналов уменьшения вероятности ошибки РB можно добиться путем увеличения М (расширения полосы пропускания). В разделе 6.1 мы показали, что РB можно уменьшить за счет кодирования k двоичных битов в одно из М ортогональных кодовых слов. Одним из основных недостатков ортогонального кодирования является неэффективное использование полосы пропускания. При наборе ортогональных кодов, включающем М=2k сигналов, требуемая ширина полосы пропускания в M/k раз больше необходимой для передачи некодированного сигнала. В этом и последующих разделах мы отойдем от рассмотрения ортогональных или антиподных свойств сигналов и сосредоточим внимание на классе процедур кодирования, известных как коды с контролем четности (parity-check codes). Эти процедуры канального кодирования относятся к структурированным последовательностям, поскольку они представляют методы введения в Исходные данные структурированной избыточности таким образом, что это позволяет обнаруживать или исправлять ошибки. Как показано на рис. 6.1, структурированные последовательности делятся на три подкатегории: блочные, сверточные и турбокоды. Блочное кодирование рассматривается в этой главе, а другие описываются в главах 7 и 8.
6.3.1. Модели каналов
6.3.1.1. Дискретный канал без памяти
Дискретный канал без памяти (discrete memoryless channel — DMC) характеризуется дискретным входным алфавитом, дискретным выходным алфавитом и набором условных вероятностей 
где i представляет модулятор M-арного входного символа, j — демодулятор Q-арного выходного символа, a P(i\j) — это вероятность приема символа j при переданном символе i. Каждый выходной символ канала зависит только от соответствующего входного символа, так что для данной входной последовательности 
условную вероятность соответствующей выходной последовательности Z = z1,z2,…,zm,…, zn можно записать следующим образом.
(6.12)
Если же канал имеет память (т.е. в пакете данных имеются помехи или канал подвергается воздействию замирания), условную вероятность последовательности Z нужно выражать как совместную вероятность всех элементов последовательности. Уравнение (6.12) — это условие отсутствия памяти у канала. Поскольку считается, что шум в канале без памяти влияет на каждый символ независимо от других, то в этом случае условная вероятность Z является произведением вероятностей независимых элементов.
6.3.1.2. Двоичный симметричный канал
Двоичный симметричный канал (binary symmetric channel — BSC) является частным случаем дискретного канала без памяти, входной и выходной алфавиты которого состоят из двоичных элементов (0 и 1). Условные вероятности имеют симметричный вид.
и (6.13)
Уравнение (6.13) выражает так называемые вероятности перехода. Иными словами, при передаче канального символа вероятность принятия его с ошибкой равна р (относительно значения энергии), а вероятность того, что он передан без ошибки, — (1-р). Поскольку на выход демодулятора поступают дискретные элементы 0 или 1, говорят, что по отношению к каждому символу демодулятор принимает жесткое решение (hard decision). Рассмотрим наиболее распространенную схему кодирования — данные в формате BPSK плюс демодуляция по принципу жесткого решения. Вероятность появления ошибки в канальном символе находится с использованием метода, обсуждавшегося в разделе 4.7.1, и дается уравнением (4.79).
Здесь EJN0 — отношение энергии канального символа к плотности помех, а функция Q(x) была определена в уравнении (3.43).
Если описанная схема жестких решений применяется в системах с бинарными кодировками, то с демодулятора на декодер поступают двоичные кодовые символы или биты канала. Поскольку декодер работает на основе жестких решений, определяемых демодулятором, декодирование в двоичном симметричном канале называется также жестким декодированием.
6.3.1.3. Гауссов канал
Определение двоичного симметричного канала можно использовать и для каналов с недискретным алфавитом. Пример — гауссов канал с дискретным входным алфавитом и непрерывным выходным алфавитом, лежащим в диапазоне (
). Этот канал добавляет шум ко всем передаваемым символам. Поскольку шум — это гауссова случайная переменная с нулевым средним и дисперсией σ2, результирующую функцию плотности вероятности принятой случайной величины z при условии передачи символа uk (правдоподобие uk) можно записать следующим образом.
(6.14)
для всех z, где k = 1,2,…, М.
В этом случае отсутствие памяти имеет то же значение, что и в разделе 6.3.1.1, а само уравнение (6.12) можно использовать при вычислении условной вероятности для последовательности Z.
Если на выходе демодулятора находится непрерывный алфавит или его квантовое приближение (с более чем двумя квантовыми уровнями), говорят, что демодулятор принимает мягкое решение (soft decision). Если в системе используется кодирование, демодулятор подает такие квантовые кодовые символы на декодер. Поскольку декодер работает на основе мягких решений, определяемых демодулятором, декодирование в гауссовом канале называется мягким.
В канале с жестким решением процесс обнаружения можно описать через вероятность символьной ошибки. Но в канале с мягкими решениями выбор детектора нельзя однозначно отнести к верному или неверному. Таким образом, поскольку определенного решения не существует, не может быть и выражения для вероятности ошибки; детектор может только определять семейство условных вероятностей или правдоподобий разных типов символов.
В принципе, декодеры с мягкими решениями можно сделать, но для блочных кодов они будут значительно сложнее декодеров с жесткими решениями; поэтому, как правило, блочные коды реализуются в системах с декодерами, работающими по принципу жесткого решения. Для свёрточных кодов реализация и жестких, и мягких решений одинаково популярна. В этой главе мы предполагаем, что каналы являются двоичными симметричными и, следовательно, декодеры используют жесткие решения. В главе 7 мы перейдем к обсуждению жесткого и мягкого декодирования для свёрточных кодов, а также продолжим обсуждение моделей канала.
6.3.2. Степень кодирования и избыточность
При использовании блочных кодов исходные данные делятся на блоки из k бит, которые иногда называют информационными битами, или битами сообщения; каждый блок может представлять любое из 2k отдельных сообщений. В процессе кодирования каждый k-битовый блок данных преобразуется в больший блок из п бит, который называется кодовым битом, или канальным символом. К каждому блоку данных кодирующее устройство прибавляет (n — k) бит, которые называются избыточными битами (redundant bits), битами четности (parity bits), или контрольными битами (check bits); новой информации они не несут. Для обозначения описанного кода используется запись (n, k). Отношение числа избыточных бит к числу информационных бит, (n — k)/k, называется избыточностью (redundancy) кода; отношение числа бит данных к общему числу бит, k/n, именуется степенью кодирования (code rate). Под степенью кодирования подразумевается доля кода, которая приходится на полезную информацию. Например, в коде со степенью 1/2, каждый кодовый бит несет 1/2 бит информации.
В этой главе и в главах 7 и 8 мы рассмотрим методы кодирования, получающие избыточность за счет увеличения необходимой ширины полосы. Например, метод защиты от ошибок, использующий код со степенью 1/2 (100%-ная избыточность), будет требовать двойной, по сравнению с некодированной передачей, полосы пропускания. В то же время, если использовать код со степенью 3/4, то избыточность составит 33%, и увеличение полосы пропускания будет всего 4/3. В главе 9 мы рассмотрим методы модуляции/кодирования для узкополосных каналов, где защита от ошибок происходит не за счет увеличения полосы пропускания, а за счет усложнения метода (и, как следствие, его аппаратной реализации).
6.3.2.1. Терминология в кодировании
Разные авторы по-разному называют элементы на выходе кодирующего устройства: кодовые биты (code bits), канальные биты (channel bits), кодовые символы (code symbols), канальные символы (channel symbols), биты четности (parity bits), символы четности (parity symbols). Вообще, по смыслу эти термины очень похожи между собой. В этой книге для двоичных кодов .термины «кодовые биты», «канальные биты», «кодовые символы» и «канальные символы» употребляются как синонимы. Следует уточнить, что названия «кодовые биты» и «канальные биты» подходят для описания только двоичных кодов. Такие общие названия, как «кодовые символы» и «канальные символы», зачастую более предпочтительны, поскольку они могут означать как двоичное, так и любое другое кодирование. Отметим, что эти понятия не следует путать с тем, что получается при группировке битов в передаваемые символы, о которых шла речь в предыдущей главе. Термины «биты четности» k «символы четности» применяются только к тем составляющим кода; которые представляют избыточные компоненты, прибавляемые к исходным данным.
6.3.3. Коды с контролем четности
6.3.3.1. Код с одним контрольным битом
Коды с контролем четности (parity-check code) для обнаружения или исправления ошибок используют линейные суммы информационных битов, которые называются символами (parity symbols), или битами четности (parity bits). Код с одним контрольным битом — это прибавление к блоку информационных битов одного контрольного бита. Этот бит (бит четности) может быть равен нулю или единице, причем его значение выбирается так, чтобы сумма всех битов в кодовом слове была четной или нечетной. В операции суммирования используется арифметика по модулю 2 (операция исключающего ИЛИ), описанная в разделе 2.9.3. Если бит четности выбран так, что результат четный, то говорят, что схема имеет положительную четность (even parity); если при добавлении бита четности результирующий блок данных является нечетным, то говорят, что он имеет отрицательную четность (odd parity). На рис. 6.8, а показана последовательная передача данных (первым является крайний справа бит). К каждому блоку добавляется один бит четности (крайний слева бит в каждом блоке), дающий положительную Четность.
а)
б)
Рис. 6.8. Проверка четности для последовательной и параллельной структуры кода: а) последовательная структура; б) параллельная структура
В приемном оконечном устройстве производится декодирование, заключающееся в проверке, дают ли нуль суммы принятых битов кодового слова по модулю 2 (положительная четность). Если полученный результат равен 1, то кодовое слово заведомо содержит ошибки. Степень кодирования такого кода можно записать как k/(k + 1). Как вы думаете, может ли декодер автоматически исправить цифру, полученную с ошибкой? Нет, это невозможно. Можно только обнаружить, что в кодовом символе присутствует нечетное количество ошибок. (Если ошибка была внесена в четное число битов, то проверка четности покажет отсутствие ошибок; данный случай — это пример необнаруженной ошибки.) Предполагая, что ошибки во всех разрядах равновероятны и появляются независимо, можно записать вероятность появления у ошибок в блоке, состоящем из я символов.
(6.15)
Здесь р — вероятность получения канального символа с ошибкой, а через
(6.16)
— обозначается число различных способов выбора из и бит j ошибочных. Таким образом, для кода с одним битом четности вероятность необнаруженной ошибки Рnd в блоке из п бит вычисляется следующим образом.
(6.17)
Пример 6.1. Код положительной четности
Нужно создать код обнаружения ошибок (4, 3) положительной четности, причем символ четности должен располагаться на крайней левой позиции кодового слова. Какие ошибки может обнаружить код? Вычислите вероятность необнаруженной ошибки сообщения, предполагая, что все символьные ошибки являются независимыми событиями и вероятность ошибки в канальном символе равна р = 10-3.
Решение
Код может выявлять все комбинации с одной или тремя ошибками. Вероятность необнаруженной ошибки равна вероятности появления где-либо в кодовом слове двух или четырех ошибок.
6.3.3.2. Прямоугольный код
Прямоугольный код (rectangular code), называемый также композиционным (product code), можно представить в виде параллельной структуры кода, изображенной на рис. 6.8, б. Код создается следующим образом. Вначале из битов сообщения строятся прямоугольники, состоящие из М строк и N столбцов; затем к каждой строке и каждому столбцу прибавляется бит четности, что в результате дает матрицу размером (М+ 1) х (N+1). Степень кодирования прямоугольного кода, k/n, может быть записана следующим образом.
Насколько прямоугольный код мощнее кода, который имеет один контрольный бит и предоставляет только возможность обнаружить ошибку? Отметим, что любая отдельная ошибка в разряде приведет к нарушению четности в одном столбце и в одной из строк матрицы. Следовательно, прямоугольный код может исправить любую единичную ошибку, поскольку расположение такой ошибки однозначно определяется пересечением строки и столбца, в которых была нарушена четность. В примере, показанном на рис. 6.8, б, размеры матрицы равны М= N = 5; следовательно, на рисунке отображен код (36, 25), способный исправлять единичные ошибки, расположенные, в любом из 36 двоичных разрядов. Вычислим для такого блочного кода с коррекцией ошибок вероятность появления неисправленной ошибки, для чего учтем все способы появления ошибки сообщения. Исходя из вероятности наличия j ошибок в блоке из п символов, записанной в выражении (6.5), можно записать вероятность ошибки сообщения, называемой также блочной ошибкой или ошибочным словом, для кода, который может исправить ошибочные комбинации, состоящие из t или менее ошибочных битов.
(6-18)
Здесь р — вероятность получения ошибочного канального символа. В примере на рис. 6.8, б код может исправить все однобитовые ошибки (t = 1) в прямоугольном блоке, состоящем из n = 36 бит. Следовательно, суммирование в уравнении (6.18) начинается с j = 2.
При достаточно малом р, наибольший вклад дает первое слагаемое суммы. Следовательно, для примера с прямоугольным кодом (36, 25) можно записать следующее.
Точная вероятность битовой ошибки РВзависит от конкретного кода и используемого декодера. Приближенные значения РB приводятся в разделе 6.5.3.
6.3.4. Зачем используется кодирование с коррекцией ошибок?
Кодирование с коррекцией ошибок можно рассматривать как инструмент, реализующий различные компромиссы системы. На рис. 6.9 приведен сравнительный вид двух кривых, описывающих зависимость достоверности передачи от отношения Eb/N0 Одна кривая соответствует обычной схеме модуляции без кодирования, а вторая представляет такую же модуляцию, но уже с использованием кодирования; Ниже подробно рассмотрено четыре компромисса, имеющие место при канальном кодировании.
Рис. 6.9. Сравнение типичной достоверности передачи при использовании схемы с кодированием и схемы без кодирования
6.3.4.1. Компромисс 1: достоверность или полоса пропускания
Представим себе, что разработана простая, недорогая система речевой связи, которая была установлена у заказчика. Система не использует кодирование с коррекцией ошибок. Пусть рабочая точка системы совпадает с точкой А на рис. 6.9 (Eb/N0 = 8 дБ, РВ — 10-2). После нескольких испытаний у заказчика появляются жалобы на качество связи; Он полагает, что вероятность появления битовой ошибки должна быть не выше 10-4. Обычным способом удовлетворения требования заказчика является сдвиг рабочей точки из точки А, например, в точку В (рис. 6.9). В то же время допустим, что Eb/N0, равное 8 дБ, — это максимальное значение, возможное в данной системе. Из рис. 6.9 видим, что один из возможных выходов из ситуации (компромиссов) — это сдвиг рабочей точки из точки А в точку С. Иными словами, «съехав» по вертикали вниз в точку С на кривой, отвечающей кодированному случаю, можно предоставить заказчику более высокую достоверность передачи данных. Чего это будет стоить? Помимо введения новых компонентов (кодера и декодера), это приведет к увеличению необходимой полосы пропускания. Кодирование с коррекцией ошибок требует избыточности. Если предположить, что связь будет происходить в реальном времени (так что сообщения не могут задерживаться), добавление избыточных битов потребует увеличения, скорости передачи и, конечно же, большей полосы пропускания.
6.3.4.2. Компромисс 2: мощность или полоса пропускания
Допустим, заказчику установлена система без кодирования £ рабочей точкой, совпадающей с точкой D на рис. 6.9 (Eb/N0 = 14 дБ, РB = 10-6). Заказчик не имеет претензий к качеству связи, но с помощью данного оборудования затруднительно получить требуемые Eb/N0 = 14 дБ. Иными словами, оборудование постоянно работает на грани отказа. Если снизить требования к Eb/N0 или мощности, то проблем с надежностью оборудования можно избежать. В контексте рис. 6.9 данные меры выглядят как сдвиг рабочей т,очки из D в E. Другими, словами, требуемое значение Eb/N0 можно получить, если применить кодирование с коррекцией ошибок. Таким образом, при фиксированном качестве связи компромисс заключается в получении большей производительности при снижении требований к мощности или Eb/N0. Чем за это приходится платить? Тем же, чем и в прошлый раз, — большей полосой пропускания.
Заметим, что в системах, где не используется связь в реальном времени, применение кодирования с коррекцией ошибок даст несколько отличные результаты. Повышение достоверности передачи или понижение потребляемой мощности (подобное описанным выше случаям 1 или 2) будет достигаться за счет увеличения времени задержки, а не за счет расширения полосы пропускания.
6.3.4.3. Эффективность кодирования
Пример компромиссных решений, рассмотренный в предыдущем разделе, позволяет понизить Eb/N0 с 14 до 9 дБ при поддержании той же достоверности передачи. В контексте этого примера и с помощью рис. 6.9 мы можем ввести понятие эффективность кодирования (coding gain). Итак, при данной вероятности битовой ошибки эффективность кодирования определяется как уменьшение Eb/N0, которое достигается при использовании кодирования. Эффективность кодирования G, как правило, выражается в децибелах.
(6.19)
Здесь (Eb/N0)u и (Eb/N0)с— требуемые некодированное и кодированное значения.
6.3.4.4. Компромисс 3: скорость передачи данных или полоса пропускания
Пусть разработана система без кодирования с рабочей точкой, совпадающей с точкой D на рис. 6.9 (Eb/N0 = 14 дБ, РB =10-6). Допустим, что с качеством данных нет никаких проблем и нет особой нужды в снижении мощности. Однако у заказчика возросли требования к скорости передачи данных. Напомним в связи с этим уравнение (5.20,6).
Если в системе ничего не менять, кроме скорости передачи данных R, то из приведенного выше выражения видно, что это приведет к уменьшению значения Eb/N0 и перемещению рабочей точки вверх, например из точки D в некоторую точку F. А теперь представим, что она «съезжает» вниз по вертикали в точку Е на кривую, которая представляет кодированную модуляцию. Возрастание скорости передачи данных плохо отражается на качестве их передачи. В то же время применение кодирования с коррекцией ошибок восстанавливает утраченное качество, сохраняя при этом прежний уровень мощности (Pr/N0). Итак, значение Eb/N0 понижено, но код способствует получению той же вероятности ошибки при сниженном значении Eb/N0. Какова цена такого увеличения скорости передачи данных или увеличения емкости? Как и раньше, это увеличение полосы пропускания.
6.3.4.5. Компромисс 4: пропускная способность или ширина полосы пропускания
Компромисс 4 сходен с компромиссом 3 в том, что оба дают возрастание пропускной способности. Метод множественного доступа, именуемый множественным доступом с кодовым разделением каналов (code-division multiple access — CDMA), который описывается в главе 12, — это один из стандартов, используемых в сотовой связи. При CDMA, когда все клиенты совместно используют общий спектр частот, каждый клиент является источником помех для других пользователей в той же ячейке или соседних. Поэтому пропускная способность (максимальное число клиентов) ячейки обратно пропорциональна значению Eb/N0 (см. раздел 12.8). При этом снижение Eb/N0 дает в итоге увеличение пропускной способности; код позволяет снизить мощности, используемые каждым клиентом, что, в свою очередь, приводит к увеличению общего числа клиентов. И снова платой за это является увеличение полосы пропускания. Но в этом случае увеличение полосы сигнала, получаемое при переходе к кодированию с коррекцией ошибок, незначительно, по сравнению с существенным увеличением полосы пропускания, получаемым при расширении спектра сигнала; поэтому при передаче данных оно не оказывает влияния на полосу пропускания.
В каждом из упомянутых выше компромиссов предполагалось использование «традиционного» кода с избыточными битами и более быстрая передача сигналов (для систем связи реального времени); следовательно, в каждом случае платой было расширение полосы передачи. В то же время существуют методы коррекции ошибок, называемые решетчатым кодированием (trellis-coded modulation), которые не требуют увеличения скорости передачи сигналов или расширения полосы частот для систем связи реального времени. (Эти методы рассмотрены в разделе 9.10.)
Пример 6.2. Связь вероятности ошибки с использованием кодирования
Сравните вероятность ошибки в сообщении для двух каналов связи — обычного и использующего кодирование с коррекцией ошибок. Пусть некодированная передача имеет следующие характеристики: модуляция BPSK, гауссов шум, Pr/N0 = 43 776, скорость передачи данных R — 4800 бит/с. Для случая с кодированием предполагается использование кода с коррекцией ошибок (15, 11), предоставляющего возможность исправления любых однобитовых ошибочных комбинаций кода в блоке из 15 бит. Будем считать, что демодулятор принимает жесткие решения и передает демодулированный код прямо на декодер, который, в свою очередь, определяет исходное сообщение.
Решение
Используем уравнение (4.79). Пусть 
и 
—вероятности символьных ошибок в канале без кодирования и в канале с кодированием, где 
— отношение энергии бита к спектральной плотности мощности шума, a — отношение энергии кодированного бита к спектральной плотности мощности шума.
Без кодирования
и
(6.20)
Для Q(x) используется следующее приближение, приведенное в уравнении (3.44).
Вероятность того, что некодированный блок сообщений 
будет принят с ошибкой, равна 1 минус произведение вероятностей того, что каждый бит будет обнаружен правильно. Таким образом,
(6.21)
С кодированием
Допустим, рассматриваемая система — это система связи реального времени, где задержки недопустимы, а скорость передачи канальных символов, или скорость передачи кодированных битов, равна Rc = 15/11 скорости некодированной передачи.
и
Для каждого кодового бита значение меньше, чем в случае с некодированными битами данных. Это объясняется тем, что скорость передачи канальных битов возросла, а мощность передатчика при этом не изменилась.
(6.22)
Сравнивая выражения (6.20) и (6.22), можно видеть, что вследствие внесения избыточности вероятность ошибки в канальном бите уменьшилась. За то же время и с теми же номинальными мощностями нужно обнаружить большее число бит; повышение производительности в результате кодирования еще не очевидно. Вычислим теперь с помощью уравнения (6.18) частоту появления ошибок в кодированном сообщении Рсм.
Суммирование начинается с j = 2, поскольку код позволяет исправлять все однобитовые ошибки в блоках из n = 15 бит. Достаточно хорошее приближение можно получить, используя только первый член суммы. Для рс используем значение, полученное из уравнения (6.22).
(6.23)
Сравнивая выражения (6.21) и (6.23), можно видеть, что вследствие применения кода с коррекцией ошибок вероятность ошибки сообщения была уменьшена примерно в 58 раз. Данный пример иллюстрирует типичное поведение систем связи реального времени при использовании кодирования с коррекцией ошибок. Введение избыточности означает увеличение скорости передачи сигналов, уменьшение энергии, приходящейся на канальный символ, и увеличение числа ошибок вне демодулятора. Преимуществом такого подхода является то, что декодер (при разумном значении ) позволяет с лихвой компенсировать слабую производительность демодулятора.
6.3.4.6. Характеристики кода при низком значении 
В конце данной главы читателю предлагается решить задачу 6.5, сходную с примером 6.2. В п. а задачи 6.5, где значение принимается равным 14 дБ, кодирование дает повышение достоверности передачи сообщения. В то же время в п. б, где значение снижается до 10 дБ, кодирование не дает улучшения; фактически происходит ухудшение. Может возникнуть вопрос, почему в п. б происходит такое ухудшение? По сути, в обоих пунктах задачи применяется одна и та же процедура. Ответ можно найти на рис. 6.9, который наглядно показывает связь между кодированными и некодированными вероятностями ошибки. Хотя в задаче 6.5 речь идет о вероятности ошибки сообщения, а на рис. 6.9 приведен график битовой ошибки, следующее объяснение остается в силе. Итак, на подобных графиках кривые пересекаются (как правило, при низких значениях ). Смысл этого пересечения (порога) в том, что у всех систем кодирования имеется ограниченная способность к коррекции ошибок. Если в блоке имеется больше ошибок, чем способен исправить код, система будет работать плохо. Представим себе, что значение снижается непрерывно. Что мы увидим на выходе демодулятора? Демодулятор будет допускать все больше и больше ошибок. Следовательно, такое постепенное уменьшение должно в конце концов создать пороговую ситуацию, когда декодер будет переполнен ошибками. При достижений этого порога снижение производительности можно объяснить поглощением энергии избыточными битами, которые не дают никакого выигрыша. Не удивляет ли читателя то, что в области (низких значений ), где больше всего следовало бы ожидать улучшения достоверности передачи, код имеет наименьшую эффективность? Впрочем, существует класс мощных кодов, называемых турбокодами (turbo code), которые позволяют повысить надежность передачи при низких значениях ; у турбо-кодов точка пересечения графиков находится значительно ниже, чем у сверточных кодов. (Турбокоды рассматриваются в разделе 8.4.)
6.4. Линейные блочные коды
Линейные блочные коды (подобные коду, описанному в примере 6.2) — это класс кодов с контролем четности, которые можно описать парой чисел (п, k) (объяснение этой формы записи приводилось выше). В процессе кодирования блок из k символов сообщения (вектор сообщения) преобразуется в больший блок из п символов кодового слова (кодовый вектор), образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов (0 и 1), код является двоичным и включает двоичные разряды (биты). Если не будет оговорено противное, наше последующее обсуждение линейных блочных кодов будет подразумевать именно двоичные коды.
k-битовые сообщения формируют набор из 2k последовательностей сообщения, называемых k-кортежами (k-tuple) (последовательностями k цифр), k-битовые блоки могут формировать 2n последовательности, также именуемые k-кортежами. Процедура кодирования сопоставляет с каждым из 2k Л-кортежей сообщения один из 2k л-кортежей. Блочные коды представляют взаимно однозначное соответствие, в силу чего 2k k-кортежей сообщения однозначно отображаются в множество из 2k л-кортежей кодовых слов; отображение производится согласно таблице соответствия. Для линейных кодов преобразование отображения является, конечно же, линейным.
6.4.1. Векторные пространства
Множество всех двоичных n-кортежей, Vn, называется векторным пространством над двоичным полем двух элементов (0 и 1). В двоичном поле определены две операции, сложение и умножение, причем результат этих операций принадлежит этому же множеству двух элементов. Арифметические операции сложения и умножения определяются согласно обычным правилам для алгебраического поля [4]. Например, в двоичном поле правила сложения и умножения будут следующими.
Сложение Умножение
Операция сложения, обозначаемая символом “
”, — это та же операция сложения по модулю 2, которая описывалась в разделе 2.9.3. Суммирование двоичных n-кортежей всегда производится путем сложения по модулю 2. Хотя для простоты мы чаще будем использовать для этой операции обычный знак +.
6.4.2. Векторные подпространства
Подмножество S векторного пространства Vn называется подпространством, если для него выполняются следующие условия.
1. Множеству S принадлежит нулевой вектор.
2. Сумма любых двух векторов в S также принадлежит S (свойство замкнутости).
При алгебраическом описании линейных блочных кодов данные свойства являются фундаментальными. Допустим, Vi и Vj — два кодовых слова (или кодовых вектора) в двоичном блочном коде (n, k). Код называется линейным тогда и только тогда, когда (Vi Vj) также является кодовым вектором. Линейный блочный код — это такой код, в котором вектор, не принадлежащий подпространству, нельзя получить путем сложения любых кодовых слов, принадлежащих этому подпространству.
Например, векторное пространство V4 состоит из следующих шестнадцати 4-кортежей.
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
Примером подмножества V4, являющегося подпространством, будет следующее.
0000 0101 1010 1111
Легко проверить, что сложение любых двух векторов подпространства может дать в итоге лишь один из векторов подпространства. Множество из 2k n-кортежей называется линейным блочным кодом тогда и только тогда, когда оно является подпространством векторного пространству Vn всех n-коргежей. На рис. 6.10 показана простая геометрическая аналогия, представляющая структуру линейного блочного кода. Векторное пространство Vn можно представить как составленное из 2n n-кортежей. Внутри этого векторного пространства существует подмножество из 2k л-кортежей, образующих подпространство. Эти 2k вектора или точки показаны разбросанными среди более многочисленных 2n точек, представляющих допустимые или возможные кодовые слова. Сообщение кодируется одним из 2k возможных векторов кода, после чего передается. Вследствие наличия в канале шума приниматься может измененное кодовое слово (один из 2n векторов пространства n-кортежей). Если измененный вектор не слишком отличается (лежит на небольшом расстоянии) от действительного кодового слова, декодер может обнаружить сообщение правильно. Основная задача выбора конкретной части кода подобна цели выбора семейства модулирующих сигналов, и в контексте рис. 6.10 ее можно определить следующим образом.
Рис. 6.10. Структура линейного блочного кода
1. Наполняя пространство Vn максимальным количеством кодовых слов, мы боремся за эффективность кодирования. Это равносильно утверждению, что мы хотим ввести лишь небольшую избыточность (избыток полосы).
2. Мы хотим, чтобы кодовые слова были максимально удалены друг от друга, так что даже если векторы будут искажены в ходе передачи, их все еще можно будет с высокой вероятностью правильно декодировать.
6.4.3. Пример линейного блочного кода (6,3)
Приведем необходимые предварительные замечания относительно кода (6,3). Он состоит из 2k = 23 = 8 векторов сообщений и, следовательно, восьми кодовых слов. В векторном пространстве V6 имеется 2n (26 = шестьдесят четыре) 6-кортежей.
Нетрудно убедиться, что восемь кодовых слов, показанных в табл. 6.1, образуют в V6 подпространство (есть нулевой вектор, сумма любых двух кодовых слов дает кодовое слово этого же подпространства). Таким образом, эти кодовые слова представляют линейный блочный код, определенный в разделе 6.4.2. Может возникнуть естественный вопрос о соответствии кодовых слов и сообщений для этого кода (6, 3). Однозначного соответствия для отдельных кодов (n, k) не существует; хотя, впрочем, здесь нет полной свободы выбора. Подробнее о требованиях и ограничениях, сопровождающих разработку кода, будет рассказано в разделе 6.6.3.
Таблица 6.1. Соответствие кодовых слов и сообщений
