Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
9.5. Помехоустойчивое кодирование и декодирование
——————————————————————————————————
Кодированием и декодированием в широком смысле называют любое преобразование сообщения в сигнал и, обратно, сигнала в сообщение путем установления взаимного соответствия. Преобразование следует считать оптимальным, если в итоге производительность источника и пропускная способность непрерывного канала окажутся равными, т. е. полностью используются возможности канала. К сожалению, такая постановка задачи не дает ответа на вопрос: что для этого надо делать? Поэтому это преобразование и разбивают на два этапа, а именно: этап модуляции—демодуляции, который позволяет перейти от непрерывного канала (радиоканала) к дискретному, и этап кодирования—декодирования в узком смысле, где все операции совершаются над последовательностью символов. Однако и само кодирование—декодирование имеет два противоположных по своим функциям этапа: устранение избыточности в получаемом от источника сигнале (экономное кодирование) и внесение избыточности в передаваемый по каналу цифровой сигнал (помехоустойчивое или избыточное кодирование) для повышения достоверности передаваемой информации.
Экономное кодирование направлено на то, чтобы передаваемый дискретный сигнал имел максимальную энтропию (максимальное количество информации на символ). Тогда для его передачи по радиоканалу с выбранным модемом потребуется минимальная полоса частот. Не рассматривая методы экономного кодирования, укажем только основные свойства дискретного сигнала, в котором полностью устранена избыточность, — это равная вероятность и независимость их появления в последовательности. В этом случае среднее количество информации на символ равно log2 m.
Примером экономного кодирования является передача речевого сигнала по цифровым каналам. Если ориентироваться только на смысловое (информационное) содержание, то можно перейти к передаче текста со скоростью 5…10 букв/с. С учетом объема алфавита в двоичном канале это потребует скорость передачи 25…50 бит/с. Если устранить избыточность, связанную с неодинаковой вероятностью их появления и их корреляцией в тексте, то, как показывают расчеты, скорость передачи может быть уменьшена до 10 бит/с. Если передавать речь в цифровой форме, используя аналого-цифровое преобразование, ориентируясь только на ширину спектра и динамический диапазон, то скорость потока двоичных символов составит 32…64 кбит/с. Такая колоссальная избыточность привела к необходимости разработки специальных кодеков речевых сигналов, называемых вокодерами, которые нашли применение при передаче речи в цифровой форме по радиоканалам. Например, в сотовых системах мобильной связи стандарта GSM скорость передачи составляет 8,5 кбит/с, причем сохраняются не только смысловое содержание, но и индивидуальные особенности говорящего. Подобные кодеки находят применение и при передаче подвижных и неподвижных изображений в цифровых телевизионных каналах.
При помехоустойчивом кодировании в поток передаваемых символов вводятся дополнительные (избыточные) символы для исправления возникающих на приемной стороне ошибок. Это требует увеличения скорости передачи по каналу, что при выбранном типе модема эквивалентно расширению полосы частот сигнала и уменьшению энергии посылки. Поэтому может возникнуть правомерный вопрос о целесообразности использования вообще избыточного кодирования. На этот вопрос дает ответ теорема Шеннона о пропускной способности непрерывного канала связи, из которой следует, что пропускная способность непрерывного канала увеличивается с расширением его полосы, но при оптимальном в широком смысле кодировании. Поэтому следует ожидать повышения достоверности передачи при заданной скорости и отношении сигнал—шум в канале при внесении избыточности. Однако ответа на вопрос: каким должен быть оптимальный кодек? — нет, да и, наверное, для сообщения, не фиксированного по длительности, не может быть. Тем не менее избыточное кодирование широко используется для повышения верности передачи, особенно в последние десятилетия, когда проблема создания сложных вычислительных устройств в малых габаритах практически решена.
Рассмотрим принципы кодирования на примере двоичного канала. Допустим, что источник обладает максимальной производительностью. Тог да обязательным условием внесения избыточности является увеличение числа переданных посылок за единицу времени по сравнению с их числом, поступающим от источника. Как вносятся избыточные символы, определяет тип кода. Наиболее просто предположить, что группе из k символов источника ставится в соответствие n символов, передаваемых по каналу. Такой код называется блочным и записывается условно как (n, k)-код. Возможны непрерывные коды, которые характеризуются тем, что операции кодирования и декодирования производятся над непрерывной последовательностью символов без разбиения ее на блоки.
Рассмотрим принципы помехоустойчивого кодирования на примере блочного двоичного кода как наиболее простого [11, 132]. Если к символам источника добавляются избыточные символы, то код называют систематическим. Если группе информационных символов ставится в соответствие новая группа символов, передаваемая по каналу, в которой информационных символов в явном виде нет, то код называется неразделимым. Теперь ответим на основной вопрос: как строить кодек, чтобы при фиксированной избыточности = r/n, где r — число проверочных символов для разделимого кода, достоверность передачи была бы максимальной? При передаче
безызбыточным примитивным кодом с числом разрядов k в каждом слове все Nр = 2k комбинаций являются разрешенными и ошибка хотя бы в одном символе приводит к тому, что одна разрешенная комбинация переходит в другую и происходит ошибка в приеме сообщения.
Введение избыточных символов приводит к тому, что полное число комбинаций увеличивается и становится равным N = 2n, причем часть из них N – Nр являются запрещенными и могут возникать только тогда, когда в канале происходят ошибки. Этот факт положен в основу обнаружения и исправления ошибок.
Введем понятие кодового расстояния. Предварительно отметим, что для оценки отличия одной кодовой комбинации от другой можно использовать расстояние Хэмминга d(Bi, Bj), определяемое числом разрядов, в которых одна кодовая комбинация отличается от другой. Для двоичного кода
где bik и bjk — k-e символы кодовых комбинаций Bi и Bj соответственно;
— символ суммирования по mod 2. Наименьшее расстояние Хэмминга для данного кода называется кодовым расстоянием. В дальнейшем его будем обозначать через d.
При независимых ошибках в канале корректирующую способность кода удается выразить через кодовое расстояние. Пусть имеется код с d = 1. Учитывая, что искажение одного символа изменяет расстояние Хэмминга на одну единицу, при применении кода с d = 1 обнаруживаются не все одиночные ошибки. Для того чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, получаем, что для обнаружения всех ошибок кратности l требуется код с
d l + 1.
Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, чем для их обнаружения. Если кратность исправляемых ошибок равна l, то кодовое расстояние должно удовлетворять условию
d 2l + 1.
Очевидно, что кодовое расстояние между разрешенными комбинациями можно сделать тем больше, чем больше избыточность. Однако при этом уменьшается длительность посылок и возрастает вероятность ошибок при их приеме. Поэтому вводят понятие эффективности избыточного кодирования как отношение вероятностей ошибочного приема кодовой комбинации из k информационных символов при передаче их примитивным и избыточным кодами:
Если используется примитивный код, то вероятность ошибочного приема кодовой комбинации
где Pош.п — вероятность ошибки в приеме одного символа при передаче сообщения примитивным кодом.
Для избыточного кода ошибка в приеме кодовой комбинации будет иметь место тогда, когда число ошибок при приеме символов превысит исправляющую способность кода tи. Вероятность такого события
где Pош.и — вероятность ошибки в приеме одного символа при передаче избыточным кодом.
Различие в Pош.п и Pош.и определяется уменьшением длительности посылки при передаче избыточным кодом в n/k раз. Величины Pош.п и Pош.и могут быть найдены, если известен вид модуляции и демодуляции, отношение Рс/N0 и длительность посылок источника.
Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния при введении избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным. К сожалению, задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, не решена. Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных п и k, которые часто используются при выяснении того, насколько построенный код близок к оптимальному.
Можно показать [133], что если существует блочный линейный код (п, k), то для него справедливо неравенство
(9.8)
называемое верхней границей Хэмминга, где [(d – 1)/2] означает целую часть числа (d – 1)/2.
Граница Хэмминга (9.8) близка к оптимальной для кодов с большими значениями k/n. Для кодов с малыми значениями k/n более точной является верхняя граница Плоткина:
r 2d – 2 – log2 (d).
Можно также показать, что существует блочный линейный код (п, k) с кодовым расстоянием d, для которого справедливо неравенство
называемое нижней границей Варшамова—Гильберта.
Таким образом, границы Хэмминга и Плоткина являются необходимыми условиями существования кода, а граница Варшамова—Гильберта — достаточным. Эти границы позволяют оценить эффективность блочных кодов и целесообразность их применения.
Линейный (п, k)-код можно получить из k линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными.
Представим базисные кодовые комбинации в виде (k×n)-матрицы
(9.9)
В теории кодирования матрица G называется порождающей. Тогда процесс кодирования заключается в выполнении операции
B = АG,
где А — вектор размерности k, соответствующий сообщению; В — вектор размерности п, соответствующий кодовой комбинации.
Таким образом, порождающая матрица (9.9) содержит всю необходимую для кодирования информацию. Она должна храниться в памяти кодирующего устройства. Для двоичного кода объем памяти равен k×n двоичных символов. При табличном задании кода кодирующее устройство должно запоминать п · 2k двоичных символов.
Две порождающие матрицы, отличающиеся друг от друга только порядком расположения столбцов, задают коды, которые имеют одинаковые расстояния Хэмминга между соответстствующими кодовыми комбинациями, а следовательно, одинаковые корректирующие способности. Такие коды называются эквивалентными.
В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие по одной единице среди информационных символов. При этом порождающую матрицу (9.9) удается записать в канонической форме:
(9.10)
где I — единичная (k × k)-подматрица; P — (k × (п – k))-подматрица проверочных символов, определяющая свойства кода. Матрица (9.10) задает систематический разделимый код. Можно показать, что для любого линейного кода существует эквивалентный систематический код.
Линейный (n, k)-код может быть задан так называемой проверочной матрицей Н размерности r × п. При этом некоторая комбинация В принадлежит коду только в том случае, если вектор В ортогонален всем строкам матрицы Н, т. е. если выполняется равенство
BHт = 0, (9.11)
где т — символ транспонирования матрицы.
Поскольку равенство (9.11) справедливо для любой кодовой комбинации, то
GHт = 0.
Каноническая форма матрицы Н имеет вид
(9.12)
где Рт — подматрица, столбцами которой служат строки подматрицы Р из соотношения (9.10); I — единичная (r × r)-подматрица.
Подставляя (9.12) в (9.11), можно получать п – k уравнений вида
(9.13)
которые называются уравнениями проверки. Из (9.13) следует, что проверочные символы кодовых комбинаций линейного кода образуются различными линейными комбинациями информационных символов. Единицы в любой j-й строке подматрицы Рт, входящей в проверочную матрицу (9.12), указывают, какие информационные символы участвуют в формировании
j-го проверочного символа.
Очевидно, что линейный (n, k)-код можно построить, используя уравнения проверки (9.13). При этом первые k символов кодовой комбинации информационные, а остальные п – k символов — проверочные, образуемые в соответствии с формулой (9.13).
С помощью проверочной матрицы сравнительно легко можно построить код с заданным кодовым расстоянием. Это построение основано на следующей теореме: кодовое расстояние линейного (n, k)-кода равно d тогда и только тогда, когда любые d – 1 столбцов проверочной матрицы этого кода линейно независимы, но некоторые d столбцов проверочной матрицы линейно зависимы.
Заметим, что строки проверочной матрицы линейно независимые. Поэтому проверочную матрицу можно использовать в качестве порождающей для некоторого другого линейного (п, п – k)-кода, называемого двойственным.
Кодирующее устройство для линейного (п, k)-кода (рис. 9.22) состоит из k-разрядного сдвигающего регистра и r = n – k блоков сумматоров по mod 2. Информационные символы одновременно поступают на вход регистра и на выход кодирующего устройства через коммутатор К. С поступлением k-го информационного символа на выходах блоков сумматоров в соответствии с уравнениями (9.13) формируются проверочные символы, которые затем последовательно поступают на выход кодера.
Процесс декодирования сводится к выполнению операции
где S — вектор размерности n – k, называемый синдромом; — вектор принятой кодовой комбинации.
Если принятая кодовая комбинация совпадает с одной из разрешенных В (это имеет место тогда, когда либо ошибки в принятых символах отсутствуют, либо при действии помех одна разрешенная кодовая комбинация переходит в другую), то
В противном случае S ≠ 0, причем вид синдрома зависит только от вектора ошибок е. Действительно,
где В — вектор, соответствующий передаваемой кодовой комбинации. При S = 0 декодер принимает решение об отсутствии ошибок, а при S ≠ 0 — о наличии ошибок. Число различных синдромов, соответствующих разным сочетаниям ошибок, равно 2n–k – 1. По конкретному виду синдрома можно в пределах корректирующей способности кода указать на ошибочные символы и исправить их.
Декодер линейного кода (рис. 9.23) состоит из k-разрядного сдвигающего регистра, n – k блоков сумматоров по mod 2, схемы сравнения, анализатора ошибок и корректора. Регистр служит для запоминания информационных символов принятой кодовой последовательности, из которых в блоках сумматоров формируются проверочные символы. Анализатор ошибок по конкретному виду синдрома, получаемого в результате сравнения формируемых на приемной стороне и принятых проверочных символов, определяет места ошибочных символов. Исправление информационных символов проводится в корректоре.
Заметим, что в общем случае при декодировании линейного кода с исправлением ошибок в памяти декодера должна храниться таблица соответствий между синдромами и векторами ошибок, содержащая 2n–k строк. С приходом каждой кодовой комбинации декодер должен перебрать всю таблицу. При небольших значениях п – k эта операция не вызывает затруднений. Однако для высокоэффективных кодов длиной п, равной нескольким десяткам, разность п – k принимает такие значения, что перебор таблицы из 2n–k строк оказывается практически невозможным. Например, для кода (63, 51), имеющего кодовое расстояние d = 5, таблица состоит из 212 = 4 096 строк.
При заданных значениях п и k существует 2k(n–k) линейных кодов. Задача заключается в выборе наилучшего (с позиции того или иного критерия) кода. Следует заметить, что до сих пор общие методы синтеза оптимальных линейных кодов не разработаны.
Циклические коды относятся к классу линейных. Поэтому для их построения, в принципе, достаточно знать порождающую матрицу.
Однако можно указать другой, более простой способ построения циклических кодов, основанный на представлении кодовых комбинаций многочленами b(х) вида
b(x) = bn–1 xn–1 bn–2 xn–2 … b1 x b0,
где bi, i = 0, 1, …, n – 1, — символы кодовой комбинации. Над данными многочленами можно проводить все алгебраические действия с учетом того, что сложение здесь осуществляется по mod 2.
Каждый циклический код (п, k) характеризуется так называемым порождающим многочленом. Им может быть любой многочлен р(х) степени п – k, который делит без остатка двучлен xn 1. Циклические коды характеризуются тем, что многочлены b(х) кодовых комбинаций делятся без остатка на р(х). Поэтому процесс кодирования сводится к нахождению по известным многочленам а(х) и р(х) многочлена b(х), делящегося на р(х), где а(x) — многочлен степени k – 1, соответствующий информационной последовательности символов.
Очевидно, что в качестве многочлена b(х) можно использовать произведение а(х)р(х). Однако при этом код оказывается несистематическим, что затрудняет процесс декодирования. Поэтому на практике, в основном, применяется следующий метод нахождения многочлена b(х).
Умножим многочлен а(х) на xn–k и полученное произведение разделим на р(х). Пусть
a(x)xn–k = m(x)p(x) c(x), (9.14)
где т(х) — частное, а с(х) — остаток. Поскольку операции суммирования и вычитания по mod 2 совпадают, то выражение (9.14) перепишем в виде
a(x)xn–k c(x) = m(x)p(x). (9.15)
Из соотношения (9.15) следует, что многочлен a(x)xn–k c(x) делится на р(х) и, следовательно, является искомым.
Многочлен a(x)xn–k имеет следующую структуру: первые п – k членов низшего порядка равны нулю, а коэффициенты остальных совпадают с соответствующими коэффициентами информационного многочлена а(х). Мно гочлен с(х) имеет степень меньше п – k. Таким образом, в найденном многочлене b(х) коэффициенты при х в степени п – k и выше совпадают с информационными символами, а коэффициенты при остальных членах, определяемых многочленом с(х), совпадают с проверочными символами.
В соответствии с формулой (9.15) процесс кодирования заключается в умножении многочлена а(х) на xn–k и нахождении остатка от деления a(x)xn–k на р(х) с последующим его сложением по mod 2 с многочленом a(x)xn–k.
Операции умножения и деления многочленов легко осуществляются линейными цепями на основе сдвигающих регистров [133]. В качестве примера на рис. 9.24, а представлена схема умножения многочлена b(х) степени п = 6 на многочлен f(x) = x3 x 1 по mod (x7 1). Нетрудно убедиться, что после семи тактов в регистре записывается многочлен b(x)f(x)mod (x7 1). При делении многочлена b(х) степени п = 6 на многочлен f(x) = x3 x2 1 (рис. 9.24, б) после семи тактов в регистре оказывается записанным остаток от деления.
На основе приведенных схем умножения и деления многочленов строятся кодирующие устройства для циклических кодов. На рис. 9.25 в качестве примера приведена схема кодера для кода (7, 4) с порождающим многочленом p(x) = x3 x2 1. В исходном состоянии ключи К1 и К2 находятся в положении 1. Информационные символы поступают одновременно на вход канала и на выход ячейки х3 сдвигающего регистра (это соответствует умножению многочлена а(х) на х3). В течение четырех тактов происходит деление многочлена а(х)х3 на многочлен р(х) = x3 x2 1. В результате в регистре записывается остаток, представляющий собой проверочные символы. Ключи K1 и K2 перебрасываются в положение 2, и в течение трех последующих тактов содержащиеся в регистре символы поступают в канал.
Циклический код может быть задан проверочным многочленом h(x): кодовая комбинация В принадлежит данному циклическому коду, если b(x)h(x) = 0 mod (xn 1). Проверочный многочлен связан с порождающим соотношением
h(x) = (xn 1)/p(x).
Задание кода проверочным многочленом эквивалентно заданию кода системой проверочных уравнений (9.13). Характерной особенностью циклического кода является то, что все проверочные уравнения можно получить из одного путем циклического сдвига индексов символов, входящих в исходное уравнение. Например, для кода (7, 4) с порождающим многочленом p(x) =
= x3 x2 1 проверочный многочлен имеет вид h(x) = x4 x3 x2 1. Проверочные уравнения получаются из условия
b(x)h(x) = 0 mod (x7 1) .
Осуществив умножение и приравняв коэффициенты при х4, х5 и х6 нулю, получим следующие уравнения, разрешенные относительно проверочных символов:
b2 = b6 b4 b3;
b1 = b5 b3 b2; (9.16)
b0 = b4 b2 b1.
В качестве примера на рис. 9.26 показана схема кодера циклического кода (7, 4), задаваемого проверочным многочленом h(x) = x4 x3 x2 1, или, что то же самое, проверочными соотношениями (9.16). В исходном состоянии ключ находится в положении 1. В течение четырех тактов импульсы поступают в регистр, после чего ключ переводится в положение 2. При этом обратная связь замыкается. Начиная с пятого такта, формируются проверочные символы в соответствии с соотношениями (9.16). После седьмого такта все проверочные символы оказываются сформированными, ключ вновь переключается в положение 1. Кодер готов к приему очередного сообщения. Символы кодовой комбинации поступают в канал, начиная с пятого такта.
Корректирующая способность кода зависит от порождающего многочлена р(х). Поэтому его выбор очень важен при построении циклического кода. Необходимо помнить, что степень порождающего многочлена должна быть равна числу проверочных символов. Кроме того, многочлен р(х) должен делить двучлен xn 1.
Обнаружение ошибок при использовании таких кодов заключается в делении многочлена b'(х) = b(x) + e(x), соответствующего принятой комбинации на р(х). Если остаток s(x) оказывается равным нулю, то считается, что ошибки нет, в противном случае фиксируется ошибка.
Пусть необходимо построить код, обнаруживающий все одиночные ошибки. В этом случае многочлен ошибок имеет вид е(х) = хi, где i = 0,
1, …, n – 1. Решение задачи заключается в нахождении такого многочлена р(х), чтобы многочлен е(х) не делился на р(х). Наиболее простым, удовлетворяющим этому требованию, является многочлен р(х) = х 1.
Аналогично можно построить код, обнаруживающий ошибки большей кратности.
Многочлен s(x) = (b(x) e(x)) mod (p(x)) = e(x) mod (p(x)) зависит только от многочлена ошибок е(х) и играет ту же роль, что и вектор-синд ром. Поэтому в принципе ошибки можно исправлять на основе таблицы соответствий между е(х) и s(x), хранящейся в памяти декодера, как при линейных нециклических кодах. Однако свойство цикличности позволяет существенно упростить процедуру декодирования.
Один из алгоритмов исправления ошибок основан на следующих свойствах синдрома циклического кода. Пусть имеется циклический код с кодовым расстоянием d, исправляющий все ошибки до кратности l = [(d – 1)/2] включительно, где [(d – 1)/2] — целая часть числа (d – 1)/2. Тогда можно показать [133], что:
— если исправляемый вектор ошибок искажает только проверочные символы, то вес синдрома будет меньше или равен l, а сам синдром будет совпадать с вектором ошибок;
— если вектор ошибки искажает хотя бы один информационный символ, то вес синдрома будет больше l;
— если s(x) — остаток от деления многочлена b(х) на р(х), то остатком от деления многочлена b(x)xi на р(х) является многочлен s(х)ximod [p(x)], другими словами, синдром некоторого циклического сдвига многочлена b(х) является соответствующим циклическим сдвигом синдрома исходного многочлена, взятого по модулю р(х).
В качестве примера на рис. 9.27 представлена схема декодера для кода (7, 4) с порождающим многочленом p(x) = x3 x2 1. Код имеет кодовое расстояние d = 3, что позволяет ему исправлять все однократные ошибки.
Принятая кодовая комбинация одновременно поступает в буферный регистр сдвига, служащий для запоминания кодовой комбинации и ее циклического сдвига, и на устройство деления на многочлен р(х) для вычисления синдрома. В исходном состоянии ключ находится в положении 1. После семи тактов буферный регистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром. Если вес синдрома больше единицы, то декодер начинает проводить циклические сдвиги комбинации в буферном регистре при отсутствии новой комбинации на входе и одновременно вычислять их синдромы s(x)ximod (p(x)) в устройстве деления. Если на некотором i-м шаге вес синдрома окажется меньше двух, то ключ переходит в положение 2, обратные связи в регистре деления разрываются. При последующих тактах ошибки исправляются путем подачи содержимого регистра деления на вход сумматора по mod 2, включенного в буферный регистр. После семи тактов работы декодера в автономном режиме исправленная комбинация в буферном регистре возвращается в исходное положение (информационные символы будут занимать старшие разряды).
Существуют и другие, более универсальные алгоритмы декодирования.
К циклическим кодам относятся коды Хэмминга, которые являются примерами немногих известных совершенных кодов. Они имеют кодовое расстояние d = 3 и исправляют все одиночные ошибки. Длина кода выбирается из условия 2n–k – 1 = n, которое имеет простой смысл: число различных ненулевых синдромов равно числу символов в кодовой последовательности. Так, существуют коды Хэмминга (2r – 1, 2r – r – 1), в частности коды (7, 4), (15, 11), (31, 26), (63, 57) и т. д.
Отметим, что ранее использованный многочлен p(x) = x3 x2 1 является порождающим для кода Хэмминга (7, 4).
Среди циклических кодов широкое применение нашли коды Боуза—Чоудхури—Хоквингема (БЧХ). Можно показать, что для любых целых положительных чисел т и l < n/2 существует двоичный код БЧХ длины n = 2m – 1 с кодовым расстоянием d 2l + 1, причем число проверочных символов
n – k ml.
Для кодов БЧХ умеренной длины и ФМ при передаче символов можно добиться значительного выигрыша (4 дБ и более) [133]. Он достигается при скоростях 1/3 k/n 3/4. При очень высоких и очень низких скоростях выигрыш от кодирования существенно уменьшается.
Иногда целесообразно использовать коды с несколько худшей корректирующей способностью по сравнению с лучшими известными кодами, но простые в реализации. К ним относятся коды, допускающие мажоритарное декодирование. Оно основано на возможности для некоторых циклических кодов выразить каждый информационный символ с помощью Q различных линейных соотношений. Решение о значении символа принимается по мажоритарному принципу. Для исправления всех ошибок до кратности l включительно необходимо иметь 2l + 1 независимых соотношений.
В некоторой области значений параметров мажоритарные коды имеют корректирующую способность, незначительно уступающую корректирующей способности кодов БЧХ. В то же время их реализация сравнительно проста.
Проиллюстрируем принцип мажоритарного декодирования на примере кода (7, 3) с проверочной матрицей
(9.17)
Рассматриваемый код является циклическим с порождающим многочленом p(x) = x4 x3 x2 1. Он имеет кодовое расстояние d = 4.
Используя матрицу (9.17), можно записать следующие соотношения для символа b1:
b1 = b3 b4 = b2 b6 = b5 b7. (9.18)
С учетом (9.18) в декодере имеется возможность четырьмя разными способами вычислить первый информационный символ:
(9.19)
где — принятая кодовая комбинация.
При отсутствии ошибок т. е. все проверочные соотношения (9.19) дают один и тот же результат. При наличии одного ошибочного символа три проверочных соотношения дают правильное значение, а соотношение, в котором участвует ошибочный символ, дает неверный результат. Принимая решение по мажоритарному принципу, декодер выдает правильный символ b1.
Пусть ошибочно приняты два символа. Если они входят в различные проверочные соотношения, то два проверочных соотношения дадут значение 1, а два других — значение 0. В этом случае декодер выдает сигнал отказа от декодирования. Если оба искаженных символа входят в одно проверочное соотношение, то все четыре проверки дают один и тот же результат. Декодер выдает правильный символ b1.
Аналогично определяются остальные информационные символы. Проверочные соотношения для символов b2 и b3 получаются из (9.19) циклической перестановкой:
Схема декодера (рис. 9.28) состоит из сдвигающего регистра, сумматоров по mod 2 и мажоритарного элемента М. Простота ее обусловлена тем, что в данном случае каждый символ кодовой комбинации участвует в одном проверочном соотношении. Код, для которого выполняется это условие, называется кодом с разделенными проверками.
Мажоритарное декодирование возможно и тогда, когда один и тот же символ участвует в нескольких проверочных соотношениях. Однако алгоритм декодирования усложняется.
Простыми в реализации являются также итеративные и каскадные коды.
Идея построения итеративных кодов заключается в следующем. Информационные символы записываются в виде таблицы из k1 столбцов и k2 строк. К каждой строке таблицы дописываются n1 – k1 проверочных символов в соответствии с некоторым кодом (n1, k1). Затем к каждому из n1 столбцов полученной таблицы добавляют n2 – k2 проверочных символов в соответствии с некоторым кодом (n2, k2). Таким образом строится код длиной n = n1n2 с числом информационных символов k = k1k2.
Можно показать, что для полученного двумерного итеративного кода кодовое расстояние d равно d1d2, где d1 и d2 — кодовые расстояния для кодов (n1, k1) и (n2, k2) соответственно.
Кодовая комбинация двумерного итеративного кода обычно передается последовательно по строкам, начиная с первой. Соответственно, декодирование ведется сначала по строкам, а затем, после приема всего двумерного блока, — по столбцам.
Проиллюстрируем построение кодовой комбинации двумерного итеративного кода. Пусть информационные символы записаны в виде таблицы
|
1 |
1 |
1 |
0 |
|
1 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
В качестве кодов (n1, k1) и (n2, k2) будем использовать коды с проверкой на четность. Тогда кодовая комбинация будет иметь вид
|
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
Легко показать, что кодовое расстояние этого кода равно 4. Код исправляет все однократные ошибки. Их координаты определяются по номерам строк и столбцов, в которых не выполняется проверка на четность. Одновременно код обнаруживает все двухкратные ошибки.
Итеративные коды характеризуются большой длиной, большим кодовым расстоянием и сравнительно простой процедурой декодирования. Недостатком их является малая скорость k/n при заданной исправляющей способности.
Каскадные коды получаются комбинированием двух или более кодов и в некоторой степени похожи на итеративные. Кодирование осуществляется следующим образом [133]. Множество k1k2 информационных символов (в дальнейшем предполагают, что они двоичные) разбивается на k2 подблоков по k1 символов. Каждый подблок из k1 символов рассматривается как символ из алфавита объемом Затем k2 подблоков кодируются кодовыми комбинациями внешнего кода (рис. 9.29), составленными из n2 подблоков по k1 двоичных символов. Наконец, каждый из n2 подблоков кодируется кодовыми комбинациями внутреннего (n1, k1)-кода. Полученное множество n2 кодовых слов внутреннего (n1, k1)-кода является кодовым словом каскадного (n1n2, k1k2)-кода. Обычно в качестве внешнего используют код Рида—Соломона с основанием обеспечивающий максимальное кодовое расстояние при заданных n2 и k1, n2 < а в качестве внутреннего — двоичный (n1, k1)-код.
Декодирование осуществляется следующим образом. Сначала декодируется внутренний код. При этом получается n2 подблоков, содержащих по k1 символов, которые декодируются внешним декодером. В результате на выходе внешнего декодера появляются k2 подблоков по k1 символов.
Декодирование двумя отдельными декодерами позволяет существенно снизить сложность по сравнению с той, которая потребуется для получения той же вероятности ошибки при одном уровне кодирования.
Каскадные коды, как и итеративные, имеют большую длину и большое кодовое расстояние. Во многих случаях они являются наилучшими среди блочных кодов. В частности, для двоичного симметричного канала при любой скорости передачи, не превосходящей пропускной способности канала, существует каскадный код, при котором вероятность ошибки может быть сколь угодно мала.
Сверточный код — это линейный рекуррентный код. В общем случае он образуется следующим образом. В каждый i-й тактовый момент времени на вход кодирующего устройства поступает k0 символов сообщения Выходные символы формируются с помощью рекуррентного соотношения из K символов сообщения, поступивших в данный и предшествующие тактовые моменты времени:
где cjνm — коэффициенты, принимающие значения 0 или 1. Символы сообщения, из которых формируются выходные символы, хранятся в памяти кодирующего устройства. Величина K называется длиной кодового ограничения. Сверточный код имеет избыточность χ = 1 – k0/n0 и обозначается k0/n0.
Типичные параметры сверточного кода: k0, n0 = 1, 2, …, 8; k0/n0 =
= 1/4, …, 7/8; K = 3, …, 10 [133].
Кодирующее устройство сверточного кода может быть реализовано с помощью сдвигающего регистра и сумматоров по mod 2. Для схемы, показанной на рис. 9.30, на каждый символ сообщения вырабатываются два символа, которые последовательно во времени через коммутатор подаются в канал. Выходные символы являются линейными функциями поступающего информационного символа и комбинации, записанной в первых двух разрядах регистра (логического состояния регистра). Связь между ячейками сдвигающего регистра и сумматорами по mod 2 удобно описывать порождающими многочленами qj(x), j = 1, 2, …, n0. Для рассматриваемого случая q1(x) = x2 1 (описывает связи верхнего сумматора) и q2(x) = x2 x 1 (описывает связи нижнего сумматора). Наличие члена xi, i = 0, 1, 2, …, в порождающем многочлене означает, что (i + 1)-й разряд регистра сдвига соединен с сумматором. Счет разрядов регистра ведется слева направо.
Сверточный код получается систематическим, если в каждый тактовый момент k0 выходных символов совпадают с символами сообщения. На практике обычно используются несистематические сверточные коды.
Различают прозрачные и непрозрачные сверточные коды. Первые характеризуются свойством инвариантности по отношению к операции инвертирования кода, которое заключается в следующем: если значения символов на входе кодера поменять на противоположные, то выходная последовательность символов также инвертируется. Соответственно, декодированная последовательность символов будет иметь такую же неопределенность в знаке, что и принятая последовательность символов, а следовательно, неопределенность знака последовательности можно устранить после декодирования сверточного кода (рис. 9.31). Указанное свойст во прозрачных кодов особенно важно для СПИ, использующих противоположные фазоманипулированные сигналы, которым свойственно явление обратной работы.
Для непрозрачного кода неопределенность знака последовательности символов приходится устранять до сверточного декодирования, что приводит к увеличению вероятности ошибок. Нетрудно показать, что сверточный код будет прозрачным, если каждый его порождающий многочлен содержит нечетное число членов.
Помимо рассмотренного способа задания сверточного кода, возможны и другие. В частности, выходные символы можно рассматривать как свертку импульсной характеристики кодера с информационной последовательностью (отсюда происходит название кода).
Для пояснения процессов кодирования и декодирования часто используют решетчатую диаграмму, представляющую собой одно из возможных изображений кодового дерева. Такая диаграмма для кодера на рис. 9.32 состоит из узлов и ветвей (ребер). Число ветвей, исходящих из узла, равно основанию кода. Число узлов равно 2K–1. Единичному символу сообщения приписываются штриховые линии, а нулевому — сплошные. Выходные символы записываются над ветвями. Надписи около узлов характеризуют логическое состояние кодирующего устройства. Каждой информационной последовательности символов соответствует определенный путь (определенная траектория) на диаграмме. Кодовая последовательность формируется путем считывания комбинаций над ветвями при прослеживании данного пути. Соответственно процесс кодирования заключается в выборе одного из путей диаграммы.
Корректирующая способность сверточного кода зависит от так называемого свободного расстояния dсв, которое, по существу, содержит ту же информацию о коде, что и кодовое расстояние для блочных кодов. Оно определяется как минимальный вес (минимальное число единиц) пути на решетчатой диаграмме, начинающегося и заканчивающегося в нулевом узле. Например, для кода k0/n0 = 1/2, K = 3 имеем dсв = 5.
В табл. 9.1 приведены порождающие многочлены оптимальных сверточных кодов с относительной скоростью передачи 1/2 и кодовым ограничением длины 3…8, а также значения свободных расстояний этих кодов.
Таблица 9.1
|
Длина кодового |
Порождающие многочлены |
Свободное расстояние |
|
3 |
q1(x) = 1 x x2 q2(x) = 1 x2 |
5 |
|
4 |
q1(x) = 1 x x2 x3 q2(x) = 1 x x3 |
6 |
|
5 |
q1(x) = 1 x x2 x4 q2(x) = 1 x3 x4 |
7 |
|
6 |
q1(x) = 1 x x2 x4 x5 q2(x) = 1 x x5 |
8 |
|
7 |
q1(x) = 1 x x2 x3 x6 q2(x) = 1 x2 x3 x5 x6 |
10 |
|
8 |
q1(x) = 1 x x2 x3 x4 x7 q2(x) = 1 x2 x5 x6 x7 |
10 |
Сверточные коды можно декодировать различными методами. Различают декодирование с вычислением и без вычисления проверочной последовательности.
Декодирование с вычислением проверочной последовательности применяется только для систематических кодов. Оно ничем не отличается от соответствующего метода декодирования блочных кодов. На приемной стороне из принятых информационных символов формируют проверочные символы по тому закону, что и на передающей стороне, которые затем сравнивают с принимаемыми проверочными символами. В результате сравнения образуется проверочная последовательность, которая при отсутствии ошибок состоит из одних нулей. При наличии ошибок на определенных позициях последовательности появляются единичные символы. Закон формирования проверочных символов выбирается таким образом, чтобы по структуре проверочной последовательности можно было определить искаженные символы.
Декодирование по принципу максимума правдоподобия сводится к задаче отождествления принятой последовательности с одной из 2N возможных, где N — длина информационной последовательности. Решение принимается в пользу той кодовой последовательности, которая в меньшем количестве позиций отличается от принятой. Метод применим для любого сверточного кода. Однако при больших значениях N он практически не реализуем из-за необходимости перебора 2N возможных кодовых последовательностей. Существенное упрощение процедуры декодирования по максимуму правдоподобия предложил А. Витерби [13]. Характерной особенностью его метода является то, что на каждом шаге декодирования запоминается только 2K–1 наиболее правдоподобных путей. Осуществляется это следующим образом. Для определенности будем рассматривать код k0/n0 = 1/2.
Пусть начальное состояние кодирующего устройства известно. Из анализа решетчатой диаграммы следует, что в любой i-й узел на любом l-м такте из начального состояния ведут несколько путей, которым соответствуют определенные кодовые последовательности. Из всех путей выберем тот, которому соответствует кодовая последовательность Bi(l), отличающаяся от принятой меньшим числом символов. Этот путь называется выжившим. Обозначим расстояние Хэмминга между последовательностями Вi(l) и через di(l). Припишем i-му узлу вес, равный di(l). Подобную процедуру проделаем для всех остальных узлов. Возьмем любой k-й узел решетчатой диаграммы в следующий тактовый момент. Он связан с двумя предшествующими узлами, например с i-м и j-м, ветвями ik и jk соответственно (см. рис. 9.32). Для нахождения правильного пути в узел k вычислим величины di(l) + Δdik и dj(l) + Δdjk, где Δdik и Δdjk — приращения расстояний Хэмминга при продолжении путей Bi(l) и Bj(l) в узел k. Эти приращения находятся по принятому на (l + 1)-м шаге сегменту последовательности и символам, соответствующим ветвям ik и jk. Если di(l) + Δdik < dj(l) + Δdjk, то ветвь ik считается истинной и записывается в память декодирующего устройства. Ветвь jk и все ей предшествующие отбрасываются. Аналогичные операции проделывают и для остальных узлов. В результате на (l + 1)-м шаге в памяти декодирующего устройства будет храниться 2K–1 путей.
Исследования показывают [13], что через l0 ≈ 5K тактов в кодовом дереве остается лишь один путь с минимальным весом. Поэтому решение о том, какое сообщение передавалось в некоторый (m + 1)-й тактовый момент, можно принимать на (m + l0)-м такте. Для уменьшения объема памяти декодирующего устройства отрезки, по которым приняты решения, стираются. Для этого же из весов всех узлов кодового дерева периодически вычитают минимальный на данном такте вес.
Для пояснения работы декодера, реализующего алгоритм Витерби, рассмотрим следующий пример. Пусть используется ранее рассмотренный код k0/n0 = 1/2 при K = 3, q1(x) = 1 x2 и q2(x) = 1 x x2. Предположим, что передавалась нулевая последовательность, а принятая последовательность имеет вид 10 00 10 00 00 … . Работу декодера иллюстрируют диаграммы (рис. 9.33, а—д), где числа в узлах характеризуют значения di(l).
На 3-м такте работы декодера (см. рис. 9.33, б) каждый из путей, «выживших» на предыдущем такте (см. рис. 9.33, а), раздваивается. Общее число путей становится равным 8. Декодер сравнивает метрики для пар путей, ведущих в каждый узел, и из каждой пары оставляет лишь лучший. Вновь число путей оказывается равным 4. Этот процесс повторяется при каждом приеме новой ветви (см. рис. 9.33, в, г, д). Заметим, что на 5-м такте (см. рис. 9.33, в) метрика нулевого пути оказывается наилучшей.
«Выживающие» пути могут отличаться друг от друга в течение многих тактов. Однако на 10-м такте (см. рис. 9.33, д) первые восемь ветвей всех «выживших» путей совпадают. В этот момент, согласно алгоритму Витерби, принимается решение о переданных символах, так как все «выжившие» пути приходят из одного узла.
Глубина (число тактов), на которой происходит слияние путей, является случайной величиной, зависящей от ошибок в принятой последовательности, и заранее не может быть вычислена. Поэтому обычно устанавливают некоторую фиксированную глубину декодирования. При этом каждый раз, обрабатывая новую ветвь, декодер выдает самый старый символ «выжившего» пути с наилучшей метрикой.
В рассмотренном случае принятая последовательность содержала два ошибочных символа, а код имел свободное расстояние, равное 5, что позволило ему исправить эти ошибки. Предположим, что принятая последовательность содержит 3 ошибочных символа и имеет вид 11 01 00 00 … . Такая комбинация ошибок оказывается неисправляемой. Отметим, что на 3-м такте (рис. 9.33, е) удаляется правильный путь, что неизбежно приводит к ошибке. Кроме того, все «выжившие» пути имеют одну и ту же первую ветвь. На 5-м такте все выжившие пути имеют одинаковые первые две ветви (рис. 9.33, ж), а на 11-м такте — первые девять ветвей (рис. 9.33, з). Хотя при декодировании возникла ошибка, выбранный ошибочный путь отличается от правильного лишь на коротком отрезке, состоящем из трех ветвей. Информационная последовательность, соответствующая выбранному пути, имеет вид 1000, ..., т. е. содержит один ошибочный символ. Рассмотренный пример описывает типичное поведение ошибочных последовательностей при использовании алгоритма сверточного декодирования Витерби.
Алгоритм Витерби обладает рядом преимуществ. При небольших значениях длины кодового ограничения декодирующее устройство оказывается достаточно простым, реализуя в то же время высокую помехоустойчивость. Так, исследования показывают, что применение сверточных кодов с K = 3, 5 и 7 при фиксированной вероятности ошибки Pош = 10–5 позволяет получить энергетический выигрыш 4…6 дБ по сравнению с системой, использующей ФМ-сигналы без кодирования. Важным преимуществом по сравнению с методом последовательного декодирования является фиксация числа вычислительных операций на один декодированный символ. Декодирование по методу Витерби особенно перспективно в каналах с независимыми ошибками.
Декодер Витерби (рис. 9.34) состоит из синхронизатора, устройства управления и тактирования, устройства для вычисления метрик ветвей, устройства для обновления и хранения метрик ветвей, устройства для обновления и хранения гипотетических информационных последовательностей и решающего устройства.
Устройство хранения и обновления метрик путей осуществляет сложение метрик ветвей с хранящимися метриками путей, проделывает необходимые сравнения и запоминает новые метрики путей.
Устройство хранения и обновления гипотетических информационных последовательностей может быть выполнено на сдвигающих регистрах, в каждом из которых хранится полная информационная последовательность символов, соответствующая одному из «выживших» путей. Их число равно числу узлов. После обработки новой ветви регистры обмениваются содержимым в соответствии с тем, какие последовательности «выживают» при сравнении. В последнюю ячейку каждого регистра поступает новый информационный символ, а самый старый символ каждого регистра поступает в выходное решающее устройство.
Выходное решающее устройство принимает решение о переданных информационных символах. Наилучшие результаты получаются, когда в качестве переданного информационного символа берется наиболее старый символ в последовательности с наименьшей метрикой. Иногда используют мажоритарный принцип: за переданный информационный символ берут чаще всего встречающийся символ из самых старых символов всех последовательностей. Устройство управления и тактирования задает необходимый ритм работы декодера.
Во многих системах, кроме основного (прямого) канала, с помощью которого сообщение передается от источника к потребителю, имеется обратный канал для вспомогательных сообщений, которые позволяют улучшить качество передачи сообщений по прямому каналу.
Наиболее распространены системы с обратной связью, в которых для обнаружения ошибок применяют избыточные коды. Такие системы называются системами с решающей обратной связью, или системами с переспросом. В качестве кодов часто используют коды с проверкой на четность, простейшие итеративные коды, циклические коды и др. Они позволяют обнаруживать ошибки при сравнительно небольшой избыточности и простой аппаратурной реализации.
Передаваемое сообщение кодируется избыточным кодом. Полученная комбинация передается потребителю и одновременно запоминается в накопителе-повторителе. Принятая последовательность символов декодируется с обнаружением ошибок. Если при этом ошибки не обнаружены, то сообщение поступает потребителю. В противном случае сообщение бракуется и по обратному каналу передается специальный сигнал переспроса. По этому сигналу проводится повторная передача забракованной кодовой комбинации, которая извлекается из накопителя-повторителя.
Можно показать, что если в обратном канале ошибки отсутствуют, то остаточная вероятность ошибочного приема кодовой комбинации имеет вид
Pост = Pн.о/(1 – Po.oш),
где Рн.о — вероятность необнаруженной ошибки (вероятность того, что переданная кодовая комбинация перешла в другую, разрешенную); Ро.ош — вероятность обнаружения ошибки (вероятность того, что вместо переданной кодовой комбинации принята какая-либо запрещенная кодовая комбинация). Вероятности Рн.о и Ро.ош можно найти, если известны свойства канала и задан код. Соответственно, эквивалентная вероятность ошибки имеет вид
Pэ ≈ Pн.о/k(1 – Po.oш),
где k — число информационных символов в кодовой комбинации. Среднее число передач одного сообщения определяется следующим образом:
Qп = 1/(1 – Po.oш).
Несмотря на то, что обратный канал можно сделать весьма помехоустойчивым (обычно скорость передачи информации в обратном канале значительно меньше, чем в прямом), тем не менее, существует конечная вероятность того, что сигнал переспроса будет принят как сигнал подтверждения, и наоборот. В первом случае сообщение не поступает потребителю, а во втором случае оно поступает дважды. Одним из средств борьбы с ошибками в обратном канале, приводящими к потере сообщения, является использование несимметричного правила декодирования, при котором вероятность ошибочного приема сигнала переспроса существенно меньше вероятности ошибочного приема сигнала подтверждения. Например, сигнал переспроса передается кодовой комбинацией из п единичных символов, а сигнал подтверждения — комбинацией из n нулей. При приеме кодовой комбинации, содержащей хотя бы одну единицу, решение принимается в пользу сигнала переспроса. Очевидно, что в этом случае вероятность ошибочного приема сигнала переспроса можно получить сколь угодно малой.
Для того чтобы к потребителю не поступали лишние сообщения, обусловленные ошибочным приемом сигналов подтверждения, передаваемые кодовые комбинации либо снабжаются номерами, либо дополняются опознавательными символами, по которым можно узнать, передается кодовая комбинация в первый раз или она повторяется. При этом принятая повторная комбинация при отсутствии сигнала переспроса стирается и не поступает потребителю. Возможны и другие способы борьбы с ошибками такого рода.
Системы с решающей обратной связью весьма эффективны в случае каналов с замираниями. При ухудшении состояния канала увеличивается частота переспроса (уменьшается скорость передачи информации), но вероятность ошибочных сообщений, поступающих потребителю, практически не увеличивается. При улучшении состояния канала частота переспроса уменьшается. Таким образом, система как бы автоматически приспосабливается к состоянию канала связи, используя все его возможности в отношении передачи информации.
Следует заметить, что применение решающей обратной связи, конечно, не увеличивает пропускную способность прямого канала, но позволяет более простыми средствами по сравнению с длинными кодами приблизить скорость передачи информации к пропускной способности канала.
Как известно [131], многопозиционные сигналы, такие как сигналы многократной ФМ и сигналы АФМ, обеспечивают высокую удельную скорость передачи информации (высокую частотную эффективность) при уменьшении энергетической эффективности, а помехоустойчивые коды поз воляют повышать энергетическую эффективность при снижении удельной скорости передачи. Сочетание методов многопозиционной модуляции и помехоустойчивого кодирования дает возможность повысить либо энергетическую эффективность без уменьшения частотной, либо частотную эффективность без снижения энергетической, а в ряде случаев — оба параметра. Задача заключается в формировании таких сигнальных последовательностей, которые можно достаточно плотно разместить в многомерном пространстве (для обеспечения высокой частотной эффективности) и в то же время разнести на достаточно большие расстояния (для обеспечения высокой энергетической эффективности). Такие последовательности, построенные на базе помехоустойчивых кодов и многопозиционных сигналов с плотной упаковкой, называются сигнально-кодовыми конструкциями.
В качестве помехоустойчивого кода обычно используются каскадные, итеративные и сверточные коды, а в качестве многопозиционных сигналов — сигналы многократной ФМ и сигналы АФМ.
Для согласования кодека двоичного помехоустойчивого кода и модема многопозиционных сигналов используется манипуляционный код, при котором большему расстоянию по Хэммингу между кодовыми комбинациями соответствует большее расстояние между соответствующими им сигналами. Этому требованию частично удовлетворяет код Грея. Возможны и другие способы такого преобразования.
На рис. 9.35 показана структурная схема одной из возможных систем с многоуровневой ФМ и помехоустойчивым кодированием. Сформированные на выходе помехоустойчивого кодера комбинации преобразуются в кодере Грея в последовательность кодовых комбинаций длины m, которые и определяют начальную фазу радиоимпульса фиксированной длительности на выходе фазового модулятора. На приемной стороне принятый сигнал сначала синхронно детектируется фазовым модулятором. Полученная при этом последовательность символов преобразуется декодерами Грея и помехоустойчивого кода в сообщение.
Применение сигнально-кодовых конструкций позволяет существенно приблизиться к границе эффективности, определяемой пропускной способностью канала.
До сих пор предполагалось, что кодовые комбинации принимаются посимвольно, т. е. на приемной стороне вначале выносится решение о каждом символе кодовой комбинации, а затем по совокупности n принятых символов принимается решение о том, какая кодовая комбинация была передана.
При избыточных кодах такая двухэтапная процедура принятия решения оказывается неоптимальной. Объясняется это тем, что процесс демодуляции является необратимой операцией и может сопровождаться потерей информации. Действительно, после принятия решения о символе ни соответствующий элемент сигнала, ни фактическое значение результата обработки этого символа (значение апостериорной вероятности или функции правдоподобия) в дальнейшем процессе приема (при декодировании) не принимаются во внимание. В то же время их учет мог бы привести к уменьшению вероятности ошибочного декодирования кодовой комбинации.
Вся информация, содержащаяся в принимаемом сигнале, будет наиболее полно использована, если отказаться от посимвольного приема и демодулировать кодовую комбинацию в целом.
Для идеализированного двоичного канала с постоянными параметрами и помехой типа гауссовского белого шума оптимальный алгоритм «приема в целом» совпадает с алгоритмом (3.124), если все 2k возможных сигналов в точности известны, или с алгоритмом (3.149), если начальная фаза сигнала, соответствующего кодовой комбинации, случайна, но сохраняется в процессе приема всей кодовой комбинации. При этом сигнал si(t) понимают как сигнал, соответствующий всей кодовой комбинации.
Можно показать, что при использовании кода с избыточностью помехоустойчивость «приема в целом» выше помехоустойчивости поэлементного приема с исправлением ошибок, однако уступает помехоустойчивости поэлементного приема с обнаружением ошибок и переспросом по обратному каналу. При использовании кода без избыточности «прием в целом» не имеет преимуществ по сравнению с поэлементным приемом.
В общем случае вычислить вероятность ошибочного приема кодовой комбинации трудно. Однако иногда, например при использовании ортогональных, биортогональных и симплексных кодов, эту вероятность можно выразить через интегралы, которые можно определить численными методами.
Недостатком «приема в целом» является то, что он требует значительно более сложной аппаратуры по сравнению с поэлементным приемом. В частности, для его реализации требуется 2k корреляторов. Очевидно, что при достаточно эффективном коде (такой код является длинным) «прием в целом» технически нереализуем. Например, если используется (n, k)-код c k = 10, то демодулятор, реализующий «прием в целом», будет состоять из 1024 корреляторов или согласованных фильтров.
В связи с трудностями построения оптимального демодулятора для «приема в целом» большое внимание уделяется алгоритмам приема, которые не используют всю информацию о принятом сигнале, но допускают меньшие потери по сравнению с поэлементным приемом. Такие алгоритмы являются двухэтапными, как и при поэлементном приеме. Однако на первом этапе решение о переданном символе не принимается, а запоминаются значения напряжений на выходах корреляторов или согласованных фильтров, предназначенных для приема различных символов, из которых составляются кодовые комбинации. Такой вид решения называется «мягким». Как известно, эти напряжения пропорциональны логарифму функций правдоподобия и несут информацию о степени соответствия принятого сигнала тому или иному символу. Их использование при дальнейшей обработке (декодировании) и позволяет получить лучшие результаты по сравнению с поэлементным приемом.
В реальных системах выходные напряжения обычно квантуются и представляются числами, т. е. вместо оптимального аналогового декодирования по максимуму правдоподобия используют цифровое декодирование. Цифровое декодирование уже при восьми уровнях квантования практически дает такие же результаты, что и аналоговое декодирование [133]. В то же время оно значительно проще в реализации.
Существуют и другие методы приема, занимающие промежуточное положение между поэлементным приемом и «приемом в целом», например прием по наиболее надежным символам. В его основу положен тот факт, что при применении кода с кодовым расстоянием d любую его комбинацию можно декодировать, если «стереть» d – 1 символ. Устройство приема состоит из двух решающих схем. Первая из них вычисляет апостериорные вероятности и принимает предварительно решение о переданном символе. Полученная последовательность символов подается на вторую решающую схему, куда также поступает информация об апостериорных вероятностях. Декодирование выполняется по п – d + 1 наиболее надежным (имеющим большие значения апостериорной вероятности) символам.
Описанный метод дает лучшие результаты, чем поэлементный прием, так как в нем частично используется информация об апостериорных вероятностях, но уступает приему в целом, так как информация о d – 1 менее надежных символах не используется.