66630

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ И ПЕРЕМЕЖЕНИЕ. ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-08-25

632.57 KB

44 чел.

 

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ И ПЕРЕМЕЖЕНИЕ

 

ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

 

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

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

Упрощенная структурная схема системы передачи дискретных сообщений, с помехоустойчивым кодированием, изображена на рис.3.1. Здесь рассматривается случай блокового кодирования. Источник двоичной информации вырабатывает последовательность символов сообщения со скоростью Rсим/с. Эти символы группируются в блоки длиной k символов. В каждом блоке добавляется r= (n — k) дополнительных символов и образуется кодовое слово (n ,k) избыточного блокового кода. Эти избыточные символы иногда называют проверочными. Так как каждое слово, содержащее n символов, переносит только k бит информации, то скорость передачи на выходе кодера равна k/n  сим/с. Величина k/n   носит название кодовой скорости. Таким образом, в кодере осуществляется преобразование слова сообщения k в кодовое слово   n

 

  

 

путем соответствующим образом подобранных проверочных символов.

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

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

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

В декодере осуществляется обратная операция: по принятой последовательности символов определяется наиболее вероятное переданное кодовое слово. Если все переданные кодовые слова равновероятны, а канал связи не имеет памяти, то в качестве наиболее вероятного переданного слова при жестких решениях в демодуляторе выбирается то, которое ближе всех в смысле расстояния Хэмминга находится к принятому кодовому слову. Расстояние Хэмминга между последовательностями Y и Z оценивается как вес (число двоичных единиц) слова, образованного посимвольным сложением по модулю 2 последовательностей Y и Z.  (Y=101011,Z=011001, Z+Y=110010, расстояние= 3)

Наиболее характерной ситуацией использования кодирования является передача дискретных сообщений в реальном времени при ограниченной мощности передатчика. Это означает, что n-символьное кодовое слово должно быть передано за время, равное времени выдачи k символов источником сообщения. Если это условие не выполняется, то кодирование не имеет смысла, поскольку последовательность передаваемых символов сообщения может быть считана с меньшей скоростью. В результате характеристики помехоустойчивости могут быть улучшены за счет увеличения энергии передаваемых символов. Пусть мощность передатчика равна P, а длительность сообщения, содержащего k символов, равна Т. Тогда энергия сигнала, приходящаяся на слово сообщения, равна РТ.

В случае блокового избыточного кодирования имеющаяся энергия распределяется на n символов, поэтому энергия, приходящаяся на кодовый символ, равна РТ/n. Так как n>k, то при использовании кодирования энергия, приходящаяся на символ, уменьшается. Это приводит к тому, что в системе с избыточным кодированием, вероятность ошибки на символ оказывается выше, чем в системе без кодирования. Если код обладает высокой корректирующей способностью, то благодаря наличию избыточных символов эти потери «отыгрываются» и обеспечивается дополнительный выигрыш, который принято называть энергетическим выигрышем кодирования (ЭВК). ЭВК является количественной мерой эффективности кодирования. Его значения оценивают, сопоставляя энергетические затраты на передачу одного бита при фиксированных вероятностях ошибочного приема либо символа, либо бита сообщения в системах с кодированием и без кодирования. Существующие к настоящему времени коды с избыточностью, корректирующие коды, можно разбить на два широких класса: блоковые и сверточные.

 

 

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

 

Если обозначить вероятность ошибки при приеме символов в системах без кодирования и с блоковым кодированием соответственно p0, и p1, то вероятности ошибочного приема в системе без кодирования и с кодированием будут определяться соответственно выражениями:

 

 

— количество возможных конфигураций из n символов, содержащих i ошибок

k- длина блока без кодирования

n- длина  кодированного блока

r=n-k число проверочных символов

t- кратность исправляемых ошибок

Здесь предполагается, что код имеет минимальное Хэммингов расстояние dmin и исправляет все ошибки кратности

Между параметрами n, k и t блокового кода существует определенное соотношение, устанавливаемое так называемой границей Хэмминга

 

Коды, для которых соотношение (3.3) выполняется строго, называются совершенными. Примером совершенных кодов служит код Хэмминга, исправляющий одиночные ошибки, и код Голея. Другие коды могут исправлять некоторые конфигурации ошибок, кратность которых превышает t. Для этих кодов (3.3) следует трактовать как полезную верхнюю границу.

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

 

 

 

В классе циклических кодов наиболее важен подкласс так называемых кодов БЧХ. Эти коды могут быть построены для широких диапазонов длины блока, кодовой скорости и исправляющей способности. В частности, если t — кратность исправляемых ошибок в пределах блока, m — произвольное целое число, то длина кодового слова, количество проверочных символов и кодовое расстояние удовлетворяют соотношениям:

 

 

В табл.3.2 в качестве примера приведены соотношения между;: . параметрами некоторых кодов БЧХ. Отметим, что при t=1 параметры n и k соответствуют параметрам кода Хэмминга. Иначе говоря, код Хэмминга также является кодом БЧХ, исправляющим одиночные ошибки.

КОДЫ РИДА-СОЛОМОНА

Коды Рида — Соломона (коды PC) относятся к классу недвоичных кодов БЧХ. В кодере сообщение, состоящее из k q-ичных символов, выбираемых из алфавита, содержащего q=2 символов, преобразуется в кодовое слово РС-кода, содержащее и двоичных символов. Поскольку обычны входного и выходного алфавитов равны степени 2, то входные и выходные символы могут быть представлены m-разрядными двоичными словами. Таким образом, входное сообщение можно рассматривать как km-разрядное слово, а выходное кодовое слово — как nm-разрядное двоичное слово. Длина кода РС равна n=q-1.

КОД ГОЛEЯ

Этот код относится к числу наиболее интересных. Он позволяет исправить ошибки высокой кратности и является также совершенным кодом. Код Голея (23,12) является циклическим и исправляет все конфигурации ошибок, кратность которых не превышает трех. С кодом Голея (23,12) связан код (24,12), который образуется добавлением к кодовым словам кода (28,12) дополни тельного проверочного символа. Коды (23,12) и (24,12) имеют минимальное кодовое расстояние, равное соответственно 7 и 8. Поэтому код (24,12), кроме исправления ошибок кратности 3, обеспечивает обнаружение ошибок кратности 4 при незначительном изменении кодовой скорости. Код (24,12) относится в числу наиболее распространенных.

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

                                      

   СВЕРТОЧНЫЕ КОДЫ

Сверточные (или рекуррентные) коды отличаются от блоковых кодов структурой. В блоковом коде n символов кода, формируемых кодером  любой выбранный интервал времени, зависят только от k информационных символов, поступивших на его вход в течение этого же интервала времени. В сверточном коде блок из n символа кода, формируемых кодером в любой выбранный интервал времени, зависит не только от k информационных символов, поступивших на его вход в течение этого же интервала времени, но и от информационных символов, поступивших в течение (К — 1) предыдущих интервалов. Параметр К называется длиной кодового ограничении. Для сверточных кодов значение параметров n и k выбираются .малыми. Сверточные коды могут использоваться для исправления случайных ошибок, ошибок, группирующихся в пакеты, и для тех и, других. Кодер двоичного сверточного кода содержит kK-разрядный регистр и n сумматоров по mod2. Обобщенная структурная схема кодера сверточного кода приведена на рис.3.3.

На рис.3.4 приведены пример кодера сверточного кода с параметрами k=1, n=2, К=З, 1/2. Информационные символы поступают на вход регистра, а символы кода формируются на выходе коммутатора. Коммутатор (КМ) последовательно опрашивает выходы сумматоров по mod 2 в течение интервала времени, равного длительности информационного символа (бита).

Схема подключения сумматоров по mod2, значения k ,п и К полностью описывают сверточный код. Их можно определить с помощью генераторных векторов или многочленов. Например, сверточный код, формируемый кодером, изображенным на рис.3.4,

 

 

имеет порождающие векторы g1=111 и g2=1О1 и порождающие многочлены g1(х)=х2+х+1: и g2(х)=х2+1. Кроме того, сверточный код может быть задан импульсной характеристикой, определяемой как последовательность символов кода на выходе кодера    при подаче на его вход единственного символа 1. Легко проверить; что импульсная характеристика данного кода равна 111011. Так  операция сложения появляется линейной операцией,  сверточные коды относятся к классу линейных и выходная последовательность кодера может рассматриваться как результат свертки входной последовательности с импульсной характеристикой кодера. Отсюда и происходит название коды и метода кодирования.

Процедуры кодирования и декодирования удобно описывать с помощью так называемого кодового дерева, которое отображает последовательности на выходе кодера для любой. возможной входной последовательности. На рис.3.5 приведено кодовое дерево кодера, изображенного на рис.3.4, для блока из. пяти информационных символов. Если первый, символ принимает значение 0, то на выходе кодера формируется пара символов 00. Если первый символ принимает значение 1, то на выходе кодера формируется пара символов 11. Это показано с помощью двух ветвей, которые выходят из начального узла. Верхняя ветвь соответствует 0, нижняя — 1. В каждом из последующих узлов ветвление происходит аналогичным образом: из каждого узла исходит две ветви, причем верхняя ветвь соответствует 0, а нижняя -1. Ветвление будет происходить вплоть до последнего символа входного блока. Вслед за ним все входные символы принимают значение 0, и образуется только одна обрывающаяся ветвь. Таким образом, каждой из возможных входных комбинаций информационных символов соответствует своя вершина на кодовом дереве. В данном случае имеется 32 вершины. С помощью кодового дерева легко построить выходную последовательность символов кода, соответствующую определенной входной последовательности. Например, входной последовательности 11010 соответствует выходная последовательность, лежащая на пути, изображенном пунктирной линией. Анализируя

 

структуру кодового дерева на рис.3.5, можно заметить, что, начиная с узлов третьего уровня, она носит повторяющийся характер. Действительно, группа ветвей, заключенных в прямоугольники, изображенные пунктирными линиями, полностью совпадают. Это означает, что при поступлении на вход четвертого символа выходной символ кода будет одним и тем же, независимо от того, каким был первый входной символ: 0 или 1. Другими словами, после первых трех групп выходных символов кода входные последовательности  будут порождать один и тот же выходной символ.

Обозначим четыре узла третьего уровня, т.е. узлы, в которых происходит третье ветвление, буквами а, b, с, d. Повторяющаяся структура ветвей имеет место и для узлов четвертого и пятого уровней, поэтому их также можно обозначить этими же буквами. Для узлов пятого уровня любой из четырех комбинаций (11,10,01, 00) первых двух входных символов будет соответствовать один и тот же выходной символ.

Таким образом, поведение кодера можно полностью описать с помощью диаграммы состояний, изображенной на рис.3.6,а или направленного графа с четырьмя состояниями (рис.3.6,б) который устанавливает однозначное соответствие между входными и выходными символами кодера. На графе сплошные линии соответствуют входному символу 0, а пунктирные — символу 1. Например, если кодер находится в состоянии а и на вход поступает 1, то на выходе декодера будет формироваться комбинация 11 (пунктирная линия) и декодер перейдет в состояние , соответствующее R,=0 и R,=1. Аналогичным образом при поступлении 0 декодер останется в состоянии а (сплошная линия) и на выходе будет формироваться комбинация 00.

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

 

 

 

 

Другим полезным способом описания кодового дерева является решетчатая диаграмма, изображенная на рис.3.7. Диаграмма берет начало из состояния а и на ней отображаются все возможные переходы при поступлении на вход очередного символа. Сплошным линиям соответствуют переходы, происходящие при поступлении символа 1 пунктирным — символа 0. При поступлении на вход двух символов кодер оказывается в одном из четырех состояний: а, b, с или б. Заметим, что решетчатая диаграмма имеет повторяющийся характер и может быть легко построена с помощью диаграммы состояний.

          

3.8. МЕТОДЫ ПЕРЕМЕЖЕНИЯ

 

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

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

Рассмотрим некоторые эффективные методы перемежения.

БЛОКОВОЕ ПЕРЕМЕЖЕНИЕ

При блоковом перемежении кодовые слова длиной n символов записываются в виде таблицы шириной W и глубиной D символов, как показано на рис.3.14.

Предположим, что W=n. Тогда строки таблицы представляют собой кодовые слова, содержащие k информационных символов и (и - k) проверочных символов. После заполнения таблицы осуществляется последовательное считывание символов по столбцам и их передача по каналу связи. В приемнике выполняется обратная процедура — последовательная запись символов по столбцам до полного заполнения таблицы. Затем производится считывание символов по строкам таблицы и их декодирование. Такой перемежитель позволяет разрушить пакет ошибок длиной , в результате чего в каждом кодовом слове будет не более одной ошибки.

Однако периодическая последовательность одиночных ошибок, отстоящих друг от друга на D символов, будет вызывать полное поражение ошибками некоторого одного слова. Задержка при выполнении процедур перемежения- деперемежения равна 2WD сим волов. Объем памяти и перемежителя и деперемежителя составляет WD символов.

Другой возможный вариант выполнения перемежителя изображен на рис.3.15. Здесь

 

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

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

МЕЖБЛОКОВОЕ ПЕРЕМЕЩЕНИЕ

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

 

 

 

Пример межблокового перемежения при В=З и И=2 показан на рис.3.16. Здесь символы i-ro, (i+1)-го и (i+2)-го входных кодовых блоков обозначены соответственно а,b,с. Согласно приведенному правилу отображения

СВЕРТОЧНОЕ ПЕРЕМЕЖЕНИЕ

 

Структурная схема сверточного перемежителя-деперемежителя приведена на рис.3.17. Предполагается, что имеется синхронизация мультиплексоров и демультиплексоров передатчика и приемника.

 

 

Демультиплексор осуществляет последовательное подключение выхода кодера к различным строкам памяти перемежителя. Мультиплексор соответственно подключает вход декодера к различным строкам памяти деперемежителя. Каждая строка памяти представляет собой регистр сдвига, количество элементов задержки которого указано соответствующим числом, вписанным в прямоугольник. Первый элемент кодированной последовательности записывается в верхнюю строку и сразу же передается по каналу связи. Записывается он также в первую строку памяти деперемежителя, обеспечивающей задержку на (В — 1)М символов. Второй элемент кодированной последовательности записывается во вторую строку памяти перемежителя, обеспечивающей задержку на М символов. Таким образом, смежные символы кодированной последовательности оказываются разнесенными на М символов. Поэтому на них не оказывают влияние пакеты ошибок, длина которых не превышает М. При приеме второй символ дополнительно задерживается на (В — 2)М символов, так что общая задержка символов составляет (В — 1)М символов. Следует отметить, что все символы кодовой последовательности после перемежения и деперемежения имеют одинаковую задержку, поэтому порядок следования символов на выходе кодера и входе декодера сохраняется одним и тем же.


 

А также другие работы, которые могут Вас заинтересовать

29249. Символ. Смысловая структура символа 53.5 KB
  Языком культуры в широком смысле этого понятия называются те средства знаки символы тексты которые позволяют людям вступать в коммуникативные связи друг с другом ориентироваться в пространстве культуры. Язык культуры это универсальная форма осмысления реальности в которую организуются все вновь возникающие или уже существующие представления восприятия понятия образы и другие подобного рода смысловые конструкции носители смысла. Основной структурной единицей языка культуры с точки зрения семиотики являются знаковые системы.Любой...
29250. Культура как смысловое поле человеческой жизнедеятельности и способ реализации творческих возможностей человека 60.5 KB
  Речь не о какомто единственном и едином способе деятельности а о целом их ансамбле таком же сложном как и система созидательных способов деятельности деятельность распредмечивания изоморфносимметрична деятельности опредмечивания. Но и зеркально симметричным и возвращает нас к исходному пункту деятельности человеку. Какими качествами он должен обладать чтобы выполнить эту функцию Человек субъект деятельности.
29251. КУЛЬТУРА ЗАПАДНОЕВРОПЕЙСКОГО СРЕДНЕВЕКОВЬЯ 53.5 KB
  В этом исторически длительном социокультурном процессе развития феодального общества вырабатывался своеобразный тип отношений человека к миру качественно отличающий его как от культуры античного общества так и от последующей культуры Нового времени эпохи буржуазного производства. Именно христианство стало основной осью складывающегося с V века в Западной Европе мира которая влияла на все стороны жизни человека его духовные приоритеты устои общества. Следование этому образцу становилось смыслом жизни каждого человека так как...
29252. Строение культуры 38 KB
  Кагану Человек общество культура являются системными объектами. Культура понимается как система высшего уровня сложности. Изоморфность филогенеза и онтогенеза свидетельствуют о том что культура есть целостновсесторонний способ очеловечивания человека и человеческого рода и отдельного его представителя в процессе обретения им таких качеств которые природе неизвестны и порождаются преобразованием биологической формы бытия в социокультурную. Таким образом первичная форма существования культуры физическая культура.
29253. Мейнстрим, субкультура и контркультура 34 KB
  Малые культурные миры называют субкультурами. Субкультура это подкультура или культура в культуре. а субкультура отличается лишь однойдвумя чертами.
29254. СУБЪЕКТ и ОБЪЕКТ КУЛЬТУРЫ 27 KB
  Субъект культуры в культурологическом понимании какаялибо социальная общность или конкретный индивид реализующий в практической деятельности культуросозидающее начало потребление и духовное освоение объектов культуры воспроизводство себя как человека определенной исторической эпохи. В культурологическом понимании объект культуры элемент фрагмент бытия культуры являющийся сферой реализации активности и историческим результатом практической деятельности субъекта культуры.
29255. ипология культуры (типы культур) 36 KB
  Типология культур строится на основании нескольких критериев: связь с религией культуры религиозные и светские; региональная принадлежность культуры культуры Востока и Запада средиземноморская латиноамериканская; региональноэтническая особенность русская французская; принадлежность к историческому типу общества культура традиционного индустриального постиндустриального общества; хозяйственный уклад культура охотников и собирателей огородников земледельцев скотоводов индустриальная культура; сфера общества или вид...
29256. Зигмунд Фрейд (1856—1939) 43.5 KB
  Перенося психоанализ на область этнографии истории религии биографий великих деятелей культуры Фрейд и его последователи рассматривают культуру как проекцию индивидуальной психики на общественный экран. Фрейд создал Венское психоаналитическое общество 1908 известность и влияние которого постепенно распространились по Европе и Америке куда Фрейд выезжал для чтения лекций. Важным вкладом Фрейда в культурологию стали его исследования так называемого подсознательного той иррациональной и темной части человеческой психики где...
29257. ФУНКЦИИ КУЛЬТУРЫ 33.5 KB
  совокупность ролей которые выполняет культура по отношению к сообществу людей. Четвертый и последующие уровни функций культуры связаны с дифференциацией культуры на специализированные функциональные сегменты: экономическая культура военная культура культура торговли религиозная культура педагогическая культура и т. системы критериев качества осуществления тех или иных социальных функций культура труда и потребления культура быта культура языка культура научного мышления культура худож.