КОДЫ С ПРОВЕРКОЙ НА ЧЕТНОСТЬ

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

а) кодовые слова в ансамбле попарно статистически независимы;

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

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

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

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

Фиг. 6.6 Кодер с проверкой на четность. Каждый разряду, -регистра с одним сумматором ни модулю 2. Замыкание ключей производится в момент

связан сумматор. Так как суммирование по модулю 2 определяется равенствами

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

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

Мы можем преобразовать эту последовательность в двоичный вектор сигнала требуемого вида, просто переводя 1 в в специальном преобразователе:

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

Из описания, приведенного выше, очевидно, что устройство, изображенное на фиг. 6.6, действительно представляет собой кодер: при заданных связях сумматоров с -регистром каждому -мерному входному вектору ставится в соответствие спой -мерный выходной вектор Ясно также, что при различном выборе связей получаются различные коды или отображения:

Рассмотрим, например, два кодера, схематически представленные на фиг. 6.7. Для обоих кодеров Будем всегда считать для удобства, что входной вектор представляет собой число в двоичной записи, причем его первая компонента равна высшему разряду числа в этой записи. Можно проверить, что оба преобразования у задаются табл. 6.1. Об кода получаются при подстановке в вместо 1

Фиг. 6.7. Два кодера с разными связями.

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

Чтобы лучше понять структуру векторов генерируемых кодером с проверкой на четность, введем в рассмотрение совокупность коэффициентов связей Будем считать по определению, что величина равна 1, если разряд -регистра, представленного на фиг. 6.6, связан с сумматором по модулю 2, и равна 0, если этот разряд и сумматор не связаны:

Например, для первого кодера, представленного на фиг. 6.7, каждый из коэффициентов связей

равен 1, а все другие коэффициенты равны 0.

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

где — компоненты вектора, наступающего на вход кодера,

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

Например,

отметим, что для любого двоичного вектора с

В этих обозначениях равенство (6.15а) можно записать более компактно:

где

Таким образом, векторы связей для первого кодера, изображенного на фиг. 6.7, имеют вид

Если представляет собой двоичный вектор, все компоненты которого, кроме компоненты равны 0, ему соответствует выходной вектор . И вообще, есть сумма по модулю 2 вектора и тех которые соответствуют ненулевым] компонентам вектора

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

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

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

Если вектор а является РР-вектором и статистически не зависит от то вектор с — а также является РР-вектором и статистически не зависит от

Этому утверждению эквивалентно следующее соотношение:

где а и -мерные двоичные векторы.

Соотношение доказывается просто. Из следует, что если то

Поэтому при тогда и только тогда, когда

Но вектор а является РР-вектором и по зависит от Поэтому при любых

и

Отсюда следует, что, как и утверждалось выше, вектор с является РР-вектором и статистически не зависит от

Используем это свойство для доказательства того, что если сообщение на входе кодера с проверкой на четность, то для рассматриваемого-ансамбля связей кодера, во-первых, вектор на выходе кодера у; является РР-векгором и, во-вторых, вектор у; и вектор соответствующий вектору на входе попарно статистически независимы. Эти два свойства будут использованы для того, чтобы показать, что

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

Доказательство того, что вектор у является РР-вектором, вытекает из следующего соотношения [см. (6.18а)]:

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

но в рассматриваемом ансамбле вектор является РР-вектором и, кроме того, обладает свойством статистической независимости от всех других векторов а следовательно, и от . В соответствии с этим для любого I вектор оказывается РР-вектором, т. е.

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

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

Поэтому можно записать

где не входит ни в ни в и, следовательно, статистически не зависит от них. Так как является РР-вектором и статистически не зависит от то вектор тоже является РР-вектором и статистически не зависит

от векторов . В самом деле, для любых -мерных двоичных векторов а, выполняется соотношение

Поэтому

При доказательстве мы предполагали, что Если, наоборот, то статистическая независимость векторов доказывается аналогично после перестановки индексов .

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

где [согласно (5.36)]

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

Коды сигналов с несколькими значениями амплитуды. Кодеры с проверкой на четность позволяют также избежать необходимости запоминать экспоненциально большое число сигналов в случаях, когда при передаче по каналам с большим отношением сигнал/шум на степень свободы компоненты векторов сигналов принимают много значений. Кодер, пригодный для таких ситуаций, представлен на фиг. 6.8. В случае когда число возможных значений амплитуд сигнала (букв алфавита) А, принимаемых символами является целой степенью 2, число разрядов -регистра равно

а не N. Здесь, как и ранее, означает размерность совокупности сигналов

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

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

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

где определяется формулой а величина А является степенью числа два и

Только что рассмотренная простая стратегия кодирования близка к экспоненциально оптимальной при тех отношениях сигнал/шум на степень свободы, при которых значение даваемое соотношением достаточно хорошо аппроксимирует верхнюю оценку , данную Шенноном (фиг. 5.17). Если удовлетворительная аппроксимация не может быть достигнута для значений А, представляющих собой степень 2, или при одинаковых можно выйти из затруднения, переходя к более сложным процедурам, для которых Например, если при получается удовлетворительная аппроксимация, можно положить и использовать преобразователь вида

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

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

В этом разделе мы покажем, что любой двоичный код с проверкой на четность также обладает этим свойством.

В начале доказательства инвариантности отметим, что при сложении по модулю 2 произвольного -мерного двоичного вектора

с любым из векторов на выходе кодера компонента вектора у заменяется на дополнительную при и остается неизменной при Под «дополнением» мы будем понимать преобразование

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

и поскольку

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

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

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

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

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

где -векторы связей рассматриваемого частного кода. Ключевым местом в доказательстве соотношения является следующее свойство, вытекающее из (6.28):

Две совокупности векторов , где а — любой вектор, принадлежащий состоят из одних и тех же векторов. Например, для следующей совокупности векторов

полагая полупим

Совокупность отличается от совокупности лишь порядком расположения векторов.

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

Доказательство соотношения основано на свойстве замкнутости. Согласно

Если выбрать то

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

Приравнивая правые части соотношений (6.29а) и (6.29в), находим что и требовалось доказать.

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

К сожалению, в случае кодов для сигналов с большим числом амплитуд из-за асимметрии преобразования вероятность не инвариантна относительно изменения . Сильную зависимость вероятности ошибки от тк для таких кодов в принципе можно ослабить, используя процедуру «вычеркивания» кодов. Например, если вероятность ошибки для кода с сигналами размерности используемого для передачи равновероятных сообщений, содержащих К бит информации [сокращенно ], то

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

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

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

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

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

где

Чтобы понять, как образуются такие совокупности сигналов, рассмотрим случай Положим и выберем векторы связей, кодера с проверкой на четность равными

Тогда, согласно совокупность имеет вид

Соответствующие двоичные векторы равны

Очевидно, что скалярное произведение любых двух векторов равно

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

векторов отличаются их координат, откуда в свою очередь и следует ортогональность векторов

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

где введено обозначение

Последний вектор связей равен

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

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

Согласно (6.33б),

В силу ортогональности (она предполагается по индукции) -мерных векторов имеем

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

(кликните для просмотра скана)

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

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

Доказательство того, что совокупность векторов сигналов, получаемая таким усечением, образует симплекс, тривиально. Обозначим через исходную совокупность ортогональных векторов сигналов длины а через усеченную совокупность; нетрудно видеть, что вклад компоненты в произведение равен Поэтому

Заменив в соотношении на , а на получим определение симплекса (4.99); тем самым утверждение доказано.

Кодер, генерирующий симплексные векторы в случае показан на фиг. 6.10. Векторы связей раины

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

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

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

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

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