66630

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

Доклад

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

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

Русский

2014-08-25

632.57 KB

28 чел.

 

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

 

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

 

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

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

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


 

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

42459. Adobe Photoshop. Редактирование изображений: слои, лассо, выделение 1.61 MB
  С помощью инструмента Lsso Лассо необходимо выделить гриф гитары. Обведите гриф как указано на рисунке: Скопируем гриф для этого воспользуемся буфером обмена. Нашли второй гриф Как его перемещать Для этого использовать инструмент Move Перемещение. При активном втором слое Lyer 1 схватите и перемещайте гриф: В буфере обмена еще находится наш гриф вставьте его оттуда.
42461. Мосты постоянного тока и комбинированные приборы 73 KB
  Краткие теоретические сведения Мостовые методы измерения параметров электрических цепей широко применяются в измерительной технике. Одинарные мосты как правило применяются для измерения относительно больших сопротивлений двойные − для измерения малых сопротивлений. Мост Уитстона представляет собой прибор применяемый для измерения сопротивления постоянному току сравнительным методом.
42462. ПОТЕНЦІАЛЬНА ДІАГРАМА ЕЛЕКТРИЧНОГО КОЛА 1.43 MB
  Виконати дослідження нерозгалуженого електричного кола; виконати дослідження розгалуженого електричного кола зіставити результати експериментальних та теоретичних досліджень зробити висновок відносно відповідності їх законам Ома і Кірхгофа; 3 побудувати потенціальні діаграми для одного і того ж контура у двох випадках струм в елементах контура однаковий струми в елементах контура різні. Як формулюється закон Ома для вітки електричного кола...
42464. ВИВЧЕННЯ ПРИНЦИПІВ РОБОТИ ПОРТАТИВНИХ ПРИЙМАЧІВ СИСТЕМИ ГЛОБАЛЬНОГО ПОЗИЦІОНУВАННЯ GPS 278.5 KB
  Львів 2010 Мета роботи: Вивчення основ функціонування системи глобального позиціонування технічних характеристик і режимів роботи портативних GPS приймачів фірми Lowrnce з використанням симулятора. Теоретичні відомості GPS cистема глобального позиціонування англ. Використовуючи GPSприймач можна точно визначити його позицію на поверхні Землі.
42465. Ряды. Интегралы. Ряды и произведения 149.5 KB
  Ряды и произведения Вычисление суммы ряда и произведений. Если требуется вычислить сумму бесконечного ряда то в качестве верхнего предела вводится infinity. Найти полную и Nчастичную суммы ряда общий член которого равен: n=. Найти сумму степенного ряда .
42466. Туристские ресурсы и туристская инфраструктура Кении 120 KB
  Кению по праву называют «Парадным подъездом экваториальной Африки». Пейзажи этой страны вдохновили Хемингуэя на создание повестей «Зелёные холмы Африки» и «Снега Килиманджаро». Здесь охотились и отдыхали Теодор Рузвельт и Уинстон Черчилль.
42467. Деление напряжения на сопротивлениях. Потенциометры 138 KB
  В цепях, в которых сопротивление нагрузки больше сопротивлений имеющихся в распоряжении реостатов, ток через нагрузку можно регулировать, изменяя напряжение на ней. В цепях переменного тока эта задача решается с помощью трансформатора, в цепях постоянного тока − с помощью делителя напряжения (потенциометра)