линейные систематические блочные коды циклические коды каскадные коды сверточные коды
Классификация помехоустойчивых кодов
С постоянным весом
В блочных кодах информационная последовательность на входе кодера разбивается на отдельные блоки, которые кодируются и декодируются независимо друг от друга. Блочные коды являются равномерными, то есть все блоки содержат одинаковое число элементов кода.
В непрерывных (древовидных) кодах передаваемая последовательность образуется без предварительного разбиения информационной последовательности на независимые блоки. Процессы кодирования и декодирования являются непрерывными. Проверочные символы размещаются между информационными по определенному алгоритму. Часто последовательность на выходе кодера вообще нельзя разделить на информационные и проверочные символы. При этом каждый информационный символ влияет на формирование нескольких десятков символов выходной последовательности.
Разделимые двоичные коды делятся в свою очередь на линейные и нелинейные.
Линейными кодами называются коды, в которых сумма по модулю 2 двух или более разрешенных кодовых слов дает другое разрешенное кодовое слово.
Нелинейные коды этим свойством не обладают. К ним относятся итеративные коды. Итеративные коды – это коды с контрольным суммированием, причем каждое кодовое слово участвует в нескольких системах проверок.
Среди линейных кодов большую группу составляют циклические коды. Их отличительное свойство состоит в том, что циклическая перестановка символов кодового слова приводит к получению другого разрешенного кодового слова.
Линейные коды
Блочным линейным кодом называется (n,k) код, проверочные символы которого являются линейными комбинациями информационных символов. Здесь:
n – длина кода, то есть длина кодовых слов
k – число информационных символов
Обозначим U – последовательность из k информационных символов.
Обозначим V – кодовое слово линейного кода длиной n символов.
Кодовое слово V формируется из последовательности U по следующему правилу: 
Отношение R=k/n называется скоростью кода, а величина W=1-R – называется избыточностью кода.
Это запись образующей матрицы в канонической форме.
При заданной информационной последовательности и образующей матрице кодовое слово V получают следующим образом
Vi=Ui при 1 к слов линейного кода и могут составить его образующую матрицу. Произвольная образующая матрица может быть приведена к каноническому виду суммированием строк по mod2.
Кодовые слова Vj являются линейно-независимыми, если сумма по модулю 2 вида 
только когда все коэффициенты j равны 0.
Сумма по модулю 2 любого числа кодовых слов также является словом данного линейного кода.
Нулевая последовательность всегда является кодовым словом.
Кодовое расстояние dmin равно минимальному весу ненулевого кодового слова.
Получим укороченный код (4,2), вычеркнув первую строку и первый столбец, ставший нулевым, в матрице G. Образующая матрица укороченного кода G’ имеет вид 
Кодовое расстояние укороченного кода dmin=2.
Образующая матрица линейного кода имеет вид
Какие из приведенных последовательностей являются кодовыми словами данного кода? 
Какие из приведенных матриц являются образующими матрицами линейного кода (5,3)? 
Национальная библиотека им. Н. Э. Баумана
Bauman National Library
Персональные инструменты
Помехоустойчивое кодирование и декодирование в дискретных КПС
Содержание
Базовые понятия помехоустойчивого кодирования и декодирования
Кодированием и декодированием (в широком смысле) называют любое преобразование сообщения в сигнал и обратно, сигнала в сообщение, путем установления взаимного соответствия. Преобразование следует считать оптимальным, если в конечном итоге производительность источника и пропускная способность канала окажутся равными, т.е. возможности канала будут полностью использованы. Данное преобразование разбивается на два этапа:
В свою очередь, кодирование-декодирование делится на два противоположных по своим действиям действиям этапа:
Примером экономного кодирования является передача речевого сигнала по цифровым каналам. Если ориентироваться только на смысловое (семантическое) содержание, то можно перейти к передаче текста со скоростью 5. 10 букв в секунду. С учетом объема алфавита в двоичном канале это потребует скорость передачи 25. 50 бит/с. Если устранить избыточность, связанную с неодинаковой вероятностью появления букв и их корреляцией в тексте, то, как показывают расчеты, скорость передачи может быть уменьшена до 10 бит/с. Если передавать речь в цифровой форме, используя аналого-цифровое преобразование, ориентируясь только на ширину спектра и динамический диапазон, то скорость потока двоичных символов составит 32. 64 кбит/с. Такая избыточность привела к необходимости разработки специальных кодеков речевых сигналов, называемых вокодерами, которые нашли применение при передаче речи в цифровой форме по радиоканалам. Например, в сотовых системах мобильной связи стандарта GSM скорость передачи составляет 8,5 кбит/с, причем сохраняются не только семантическое содержание, но и индивидуальные особенности говорящего. Подобные кодеки находят применение и при передаче подвижных и неподвижных изображений в цифровых телевизионных каналах.
Принцип построения помехоустойчивых кодов
Основные параметры помехоустойчивых кодов
Если код примитивный, то ошибка возникает, когда хотя бы в одном символе при приеме произошла ошибка. Вероятность такого события равна:
Для избыточного кода ошибка в приеме кодовой комбинации будет иметь место тогда, когда число ошибок превысит исправляющую способность кода tи и ее вероятность:
Различие в Рош.п и Рош.и определяется уменьшением длительности посылки при передаче избыточным кодом в n/k раз. Величины Рош.п и Рош.и могут быть найдены, если известен вид модуляции и демодуляции, отношение P0 / N0 и длительность посылок источника.
Оценочные соотношения для параметров помехоустойчивых кодов
Задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния при введении избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным. Задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, не решена. Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных n / k, которые часто используются для выяснения того, насколько построенный код близок к оптимальному. Можно показать, что если существует блочный линейный код (n, k), то для него справедливо неравенство:
Выражение (1) называется верхней границей Хэмминга. Граница Хэмминга (1) близка к оптимальной для кодов с большими значениями n / k. Для кодов с малыми значениями n / k более точной вляется верхняя граница Плоткина:
называемое нижней границей Варшамова—Гильберта. Таким образом, границы Хэмминга и Плоткина являются необходимыми условиями существования кода, а граница Варшамова—Гильберта — достаточным. Эти границы позволяют оценить эффективность блочных кодов и целесообразность их применения.
Линейное блочное кодирование
Способы задания линейных кодов
В теории кодирования матрица G называется порождающей. Тогда процесс кодирования заключается в выполнении операции:
В противном случае S не равно 0, причем вид синдрома зависит только от вектора ошибок е. Действительно:
Строение декодера линейного кода
Декодер линейного кода (рис. 1) состоит из k-разрядного сдвигающего регистра, (n — k) блоков сумматоров по модулю 2, схемы сравнения, анализатора ошибок и корректора. Регистр служит для запоминания информационных символов принятой кодовой последовательности, из которых в блоках сумматоров формируются проверочные символы. Анализатор ошибок по конкретному виду синдрома, получаемого в результате сравнения формируемых на приемной стороне и принятых проверочных символов, определяет места ошибочных символов. Исправление информационных символов проводится в корректоре.
Циклические коды
Циклические коды относятся к классу линейных. Поэтому для их построения достаточно знать порождающую матрицу. Несмотря на это, можно указать другой, более простой способ построения циклических кодов, основанный на представлении кодовых комбинаций многочленами b(х) вида:
Поскольку операции суммирования и вычитания по модулю 2 совпадают, то выражение (9) перепишем в виде:
Устройство кодеров циклического кода
Коды Хэмминга
Коды БЧХ
Схема декодера (рис. 6) состоит из сдвигающего регистра, сумматоров по модулю 2 и мажоритарного элемента М. Простота ее обусловлена тем, что в данном случае каждый символ кодовой комбинации участвует в одном проверочном соотношении. Код, для которого выполняется это условие, называется кодом с разделенными проверками.
Мажоритарное декодирование возможно и тогда, когда один и тот же символ участвует в нескольких проверочных соотношениях. Однако алгоритм декодирования усложняется.
Итеративные коды
Легко показать, что кодовое расстояние этого кода равно 4. Код исправляет все однократные ошибки. Их координаты определяются по номерам строк и столбцов, в которых не выполняется проверка на четность. Одновременно код обнаруживает все двукратные ошибки. Итеративные коды характеризуются большой длиной, большим кодовым расстоянием и сравнительно простой процедурой декодирования. Недостатком их является малая скорость при заданной исправляющей способности.
Каскадные коды
Каскадные коды получаются комбинированием двух или более кодов и в некоторой степени похожи на итеративные. Кодирование осуществляется следующим образом.
Декодирование двумя отдельными декодерами позволяет существенно снизить сложность по сравнению с той, которая потребуется для получения той же вероятности ошибки при одном уровне кодирования.
Каскадные коды, как и итеративные, имеют большую длину и большое кодовое расстояние. Во многих случаях они являются наилучшими среди блочных кодов. В частности, для двоичного симметричного канала при любой скорости передачи, не превосходящей пропускной способности канала, существует каскадный код, при котором вероятность ошибки может быть сколь угодно мала.
Непрерывные сверточные коды
Основные параметры сверточных кодов
Устройство кодера сверточного кода
Виды и способы задания сверточных кодов
Указанное свойство прозрачных кодов особенно важно для СПИ, использующих противоположные фазоманипулированные (ФМ) сигналы, которым свойственно явление обратной работы. Для непрозрачного кода неопределенность знака последовательности символов приходится устранять до сверточного декодирования, что приводит к увеличению вероятности ошибок. Нетрудно показать, что сверточный код будет прозрачным, если каждый его порождающий многочлен содержит нечетное число членов. Помимо рассмотренного способа задания сверточного кода, возможны и другие. В частности, выходные символы можно рассматривать как свертку импульсной характеристики кодера с информационной последовательностью (отсюда и происходит название кода). Для пояснения процессов кодирования и декодирования часто используют решетчатую диаграмму, представляющую собой одно из возможных изображений кодового дерева. Такая диаграмма для кодера на рис. 10 состоит из узлов и ветвей (ребер). Число ветвей, исходящих из узла, равно основанию кода. Число узлов равно ( 2 K − 1 <\displaystyle 2^
Методы декодирования сверточных кодов
Декодирование с вычислением проверочной последовательности
Декодирование с вычислением проверочной последовательности применяется только для систематических кодов. Оно ничем не отличается от соответствующего метода декодирования блочных кодов. На приемной стороне из принятых информационных символов формируют проверочные символы по тому закону, что и на передающей стороне, которые затем сравнивают с принимаемыми проверочными символами. В результате сравнения образуется проверочная последовательность, которая при отсутствии ошибок состоит из одних нулей. При наличии ошибок на определенных позициях последовательности появляются единичные символы. Закон формирования проверочных символов выбирается таким образом, чтобы по структуре проверочной последовательности можно было определить искаженные символы.
Декодирование по принципу максимума правдоподобия
Алгоритм Витерби
Алгоритм Витерби обладает рядом преимуществ. При небольших значениях длины кодового ограничения декодирующее устройство оказывается достаточно простым, реализуя, в то же время, высокую помехоустойчивость. Так, исследования показывают, что применение сверточных кодов с К= 3, 5 и 7 при фиксированной вероятности ошибки Pош = 10 − 5 <\displaystyle =10^<-5>\,\!> позволяет получить энергетический выигрыш 4. 6 дБ по сравнению с системой, использующей ФМ-сигналы без кодирования. Важным преимуществом по сравнению с методом последовательного декодирования является фиксация числа вычислительных операций на один декодированный символ. Декодирование по методу Витерби особенно перспективно в каналах с независимыми ошибками.
Устройство декодера Витерби
Декодер Витерби (рис. 12) состоит из синхронизатора, устройства управления и тактирования, устройства для вычисления метрик ветвей, устройства для обновления и хранения метрик ветвей, устройства для обновления и хранения гипотетических информационных последовательностей и решающего устройства. Устройство хранения и обновления метрик путей осуществляет сложение метрик ветвей с хранящимися метриками путей, проделывает необходимые сравнения и запоминает новые метрики путей. Устройство хранения и обновления гипотетических информационных последовательностей может быть выполнено на сдвигающих регистрах, в каждом из которых хранится полная информационная последовательность символов, соответствующая одному из «выживших» путей. Их число равно числу узлов. После обработки новой ветви регистры обмениваются содержимым в соответствии с тем, какие последовательности «выживают» при сравнении. В последнюю ячейку каждого регистра поступает новый информационный символ, а самый старый символ каждого регистра поступает в выходное решающее устройство. Выходное решающее устройство принимает решение о переданных информационных символах. Наилучшие результаты получаются, когда в качестве переданного информационного символа берется наиболее старый символ в последовательности с наименьшей метрикой. Иногда используют мажоритарный принцип: за переданный информационный символ берут чаще всего встречающийся символ из самых старых символов всех последовательностей. Устройство управления и тактирования задает необходимый ритм работы декодера.
Применение кодов в технических системах
Системы с обратной связью
Во многих системах, кроме основного (прямого) канала, с помощью которого сообщение передается от источника к потребителю, имеется обратный канал для вспомогательных сообщений, которые позволяют улучшить качество передачи сообщений по прямому каналу. Наиболее распространены системы с обратной связью, в которых для обнаружения ошибок применяют избыточные коды. Такие системы называются системами с решающей обратной связью, или системами с переспросом. В качестве кодов часто используют коды с проверкой на четность, простейшие итеративные коды, циклические коды и др. Они позволяют хорошо обнаруживать ошибки при сравнительно небольшой избыточности и простой аппаратурной реализации. Передаваемое сообщение кодируется избыточным кодом. Полученная комбинация передается потребителю и одновременно запоминается в накопителе-повторителе. Принятая последовательность символов декодируется с обнаружением ошибок. Если при этом ошибки не обнаружены, то сообщение поступает потребителю. В противном случае сообщение бракуется и по обратному каналу передается специальный сигнал переспроса. По этому сигналу проводится повторная передача забракованной кодовой комбинации, которая извлекается из накопителя-повторителя. Можно показать, что если в обратном канале ошибки отсутствуют, то остаточная вероятность ошибочного приема кодовой комбинации имеет вид:
Вероятности Рно и Ро.ош можно найти, если известны свойства канала и задан код. Эквивалентная вероятность ошибки имеет вид:
Среднее число передач одного сообщения определяется следующим образом:
Несмотря на то, что обратный канал можно сделать весьма помехоустойчивым (обычно скорость передачи информации в обратном канале значительно меньше, чем в прямом), тем не менее, существует конечная вероятность того, что сигнал переспроса будет принят как сигнал подтверждения, и наоборот. В первом случае сообщение не поступает потребителю, а во втором случае оно поступает дважды. Одним из средств борьбы с ошибками в обратном канале, приводящими к потере сообщения, является использование несимметричного правила декодирования, при котором вероятность ошибочного приема сигнала переспроса существенно меньше вероятности ошибочного приема сигнала подтверждения. Например, сигнал переспроса передается кодовой комбинацией из п единичных символов, а сигнал подтверждения — комбинацией из n нулей. При приеме кодовой комбинации, содержащей хотя бы одну единицу, решение принимается в пользу сигнала переспроса. Очевидно, что в этом случае вероятность ошибочного приема сигнала переспроса можно получит сколь угодно малой. Для того чтобы к потребителю не поступали лишние сообщения, обусловленные ошибочным приемом сигналов подтверждения, передаваемые кодовые комбинации либо снабжаются номерами, либо дополняются опознавательными символами, по которым можно узнать, передается кодовая комбинация в первый раз или она повторяется. При этом принятая повторная комбинация при отсутствии сигнала переспроса стирается и не поступает потребителю. Возможны и другие способы борьбы с ошибками такого рода. Системы с решающей обратной связью весьма эффективны в случае каналов с замираниями. При ухудшении состояния канала увеличивается частота переспроса (уменьшается скорость передачи информации), но вероятность ошибочных сообщений, поступающих потребителю, практически не увеличивается. При улучшении состояния канала частота переспроса уменьшается. Таким образом, система как бы автоматически приспосабливается к состоянию канала связи, используя все его возможности в отношении передачи информации. Следует заметить, что применение решающей обратной связи, конечно, не увеличивает пропускной способности прямого канала, но позволяет более простыми средствами по сравнению с длинными кодами приблизить скорость передачи информации к пропускной способности канала.
Сигнально-кодовые конструкции
Как известно, многопозиционные сигналы, такие как сигналы многократной фазовой модуляции (ФМ) и сигналы амплитудно-фазовой модуляции (АФМ), обеспечивают высокую удельную скорость передачи информации (высокую частотную эффективность) при уменьшении энергетической эффективности, а помехоустойчивые коды позволяют повышать энергетическую эффективность при снижении удельной скорости передачи. Сочетание методов многопозиционной модуляции и помехоустойчивого кодирования дает возможность повысить либо энергетическую эффективность без уменьшения частотной, либо частотную эффективность без снижения энергетической, а в ряде случаев — оба параметра. Задача заключается в формировании таких сигнальных последовательностей, которые можно достаточно плотно разместить в многомерном пространстве (для обеспечения высокой частотной эффективности) и в то же время разнести на достаточно большие расстояния (для обеспечения высокой энергетической эффективности). Такие последовательности, построенные на базе помехоустойчивых кодов и многопозиционных сигналов с плотной упаковкой, называются сигнально-кодовыми конструкциями. В качестве помехоустойчивого кода обычно используются каскадные, итеративные и сверточные коды, а в качестве многопозиционных сигналов — сигналы многократной ФМ и сигналы АФМ. Для согласования кодека двоичного помехоустойчивого кода и модема многопозиционных сигналов используется манипуляционный код, при котором большему расстоянию по Хэммингу между кодовыми комбинациями соответствует большее расстояние между соответствующими им сигналами. Этому требованию частично удовлетворяет код Грея. Возможны и другие способы такого преобразования. На рис. 13 показана структурная схема одной из возможных систем с многоуровневой ФМ и помехоустойчивым кодированием. Сформированные на выходе помехоустойчивого кодера комбинации преобразуются в кодере Грея в последовательность кодовых комбинаций длины m, которые и определяют начальную фазу радиоимпульса фиксированной длительности на выходе фазового модулятора. На приемной стороне принятый сигнал сначала синхронно детектируется фазовым модулятором. Полученная при этом последовательность символов преобразуется декодерами Грея и помехоустойчивого кода в сообщение. Применение сигнально-кодовых конструкций позволяет существенно приблизиться к границе эффективности, определяемой пропускной способностью канала.
Методы приема сигналов
Прием «в целом»
До сих пор предполагалось, что кодовые комбинации принимаются посимвольно, т. е. на приемной стороне вначале выносится решение о каждом символе кодовой комбинации, а затем по совокупности n принятых символов принимается решение о том, какая кодовая комбинация была передана. При избыточных кодах такая двухэтапная процедура принятия решения оказывается неоптимальной. Объясняется это тем, что процесс демодуляции является необратимой операцией и может сопровождаться потерей информации. Действительно, после принятия решения о символе ни соответствующий элемент сигнала, ни фактическое значение результата обработки этого символа (значение апостериорной вероятности или функции правдоподобия) в дальнейшем процессе приема (при декодировании) не принимаются во внимание. В то же время их учет мог бы привести к уменьшению вероятности ошибочного декодирования кодовой комбинации. Вся информация, содержащаяся в принимаемом сигнале, будет наиболее полно использована, если отказаться от посимвольного приема и демодулировать кодовую комбинацию в целом. Можно показать, что при использовании кода с избыточностью помехоустойчивость приема «в целом» выше помехоустойчивости поэлементного приема с исправлением ошибок, однако уступает помехоустойчивости поэлементного приема с обнаружением ошибок и переспросом по обратному каналу. При использовании кода без избыточности «прием в целом» не имеет преимуществ по сравнению с поэлементным приемом. В общем случае вычислить вероятность ошибочного приема кодовой комбинации трудно. Однако иногда, например при использовании ортогональных, биортогональных и симплексных кодов, эту вероятность можно выразить через интегралы, которые можно определить численными методами. Недостатком «приема в целом» является то, что он требует значительно более сложной аппаратуры по сравнению с поэлементным приемом. В частности, для его реализации требуется 2 k <\displaystyle 2^