66630

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

Доклад

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

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

Русский

2014-08-25

632.57 KB

43 чел.

 

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

 

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

 

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

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

Упрощенная структурная схема системы передачи дискретных сообщений, с помехоустойчивым кодированием, изображена на рис.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)М символов. Следует отметить, что все символы кодовой последовательности после перемежения и деперемежения имеют одинаковую задержку, поэтому порядок следования символов на выходе кодера и входе декодера сохраняется одним и тем же.


 

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

39062. Математические пакеты и их применение в науке и производстве 34 KB
  От других продуктов аналогичного назначения например Mple Theorist компании Wterloo Mple Softwre и Mthemtic компании Wolf Reserch MTHCD компании Mthsoft отличается ориентация на создание высококачественных документов докладов отчетов статей в режиме WYSIWYG Wht You See Is Wht You Get. Преимущества MTHCD состоит в том что он не только позволяет провести необходимые расчеты но и оформить свою работу с помощью графиков рисунков таблиц и математических формул. В MTHCD`e можно не только совмещать текст и формулы но...
39063. Системы автоматизированного проектирования. Программы AutoCAD и P-CAD 67 KB
  Программы utoCD и PCD По целевому назначению программы utoCD и PCD относятся к группе: CD англ. По отраслевому назначению программы utoCD и PCD относятся к группам: ED англ. utodesk rchitecturl Desktop utoCD Revit rchitecture Suite Pirnesi rchiCD. Сравнение utoCD и PCD Характеристика utoCD PCD 1.
39064. Работа с базами данных. Язык SQL 44 KB
  Большинство современных СУБД построено на реляционной модели данных. Для получения информации из отношений таблиц базы данных в качестве языка манипулирования данными в теоретическом плане используются три абстрактных языка: язык реляционной алгебры; язык реляционного исчисления на кортежах; язык реляционного исчисления на доменах. Накопленная информация в современных информационных технологиях хранится и организованна в базах данных.
39065. Программа для бизнес-планирования производства и оказания услуг в бизнесе Project Expert 90.5 KB
  Аналитическая система Project Expert программа позволяющая прожить планируемые инвестиционные решения без потери финансовых средств предоставить необходимую финансовую отчётность потенциальным инвесторам и кредиторам обосновать для них эффективность участия в проекте. Project Expert поможет: Разработать бизнесплан развития предприятия Разработать финансовую модель проекта и компании Определить финансирование проекта. Работу с программой Project Expert можно разделить на 6 этапов: 1.
39066. Язык UML 91 KB
  На UML диаграмме примечание присоединяется к одному или нескольким элементам диаграммы. Внутри прямоугольникапримечания помещаются комментарии или ограничения относящиеся к элементу или нескольким элементам диаграммы. UML диаграммы С помощью комбинации пиктограмм строятся UML диаграммы. Рассмотрим три из них: диаграммы прецедентов диаграммы классов и диаграммы действий.
39067. Характеристика case-средства Rational Rose 138 KB
  Назначение элементов экрана интерфейса Rose: Браузер browser используется для быстрой навигации по модели. C его помощью можно документировать элементы модели Rose. Документация будет выводиться также в отчетах создаваемых в среде Rose.
39068. Работа с объектами информационных систем на платформе 1С:Предприятие 43 KB
  1С:Предприятие является универсальной системой автоматизации деятельности предприятий учреждений. За счет своей универсальности система 1С:Предприятие может быть использована для автоматизации самых разных участков экономической деятельности предприятия: учета товарных и материальных средств взаиморасчетов с контрагентами. Самыми распространенными наверное являются такие конфигурации как Бухгалтерия Бухгалтерия государственного учреждения Зарплата и кадры бюджетного учреждения Зарплата и управление персоналом Управление...
39069. Тестированию программного обеспечения с использованием языка программирования C# и NUnit-тестов 82.5 KB
  Тестовая деятельность предусматривающая эксплуатацию программного продукта носит название динамического тестирования. Статическое и динамическое тестирование дополняют друг друга и каждый из этих типов тестирования реализует собственный подход к выявлению ошибок. К четырем компонентам которые должны быть оптимизированы для целей быстрого тестирования относятся персонал процесс комплексных испытаний статическое тестирование и динамическое тестирование. 1 Для выполнения быстрого тестирования нужны хорошо подготовленные и гибкие...
39070. Использование программных продуктов CRM на российском рынке 304.5 KB
  Системы управления взаимоотношения с клиентами CRM Система управления взаимоотношениями с клиентами CRM CRMсистема сокращение от англ. CRM модель взаимодействия полагающая что центром всей философии бизнеса является клиент а основными направлениями деятельности являются меры по поддержке эффективного маркетинга продаж и обслуживания клиентов. Состав системы CRMсистема может включать в себя: Фронтальную часть обеспечивающую обслуживание клиентов на точках продаж с автономной распределенной или централизованной обработкой...