ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->ТЕМА 3  ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

Теория информации

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

 

3.1  Основные принципы помехоустойчивого кодирования информации

 

         Кодирование с исправлением ошибок представляет собой метод обработки сообщений, предназначенный для повышения надежности передачи по цифровым каналам.

         Хотя различные схемы помехоустойчивого кодирования основаны на различных математических теориях, им присущи некоторые общие свойства:

1)    использование избыточности - закодированные последовательности всегда содержат дополнительные или избыточные символы;

2)    свойство усреднения – избыточные символы зависят от нескольких информационных, т.е. информация, содержащаяся в кодовой последовательности, перераспределяется также и на избыточные символы.

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

 

         Кодер для блочных кодов делит непрерывную информационную последовательность на блоки-сообщения длиной k символов.

         Кодер канала преобразует блоки-сообщения X в более длинные последовательности Y, состоящие из n символов и называемые кодовыми словами.

         r=n-k символов, добавляемых кодером к каждому блоку-сообщению, называются избыточными (или проверочными, или контрольными). Они не несут дополнительной информации, их функции заключаются в обеспечении возможности обнаруживать и/или исправлять ошибки, возникающие в процессе передачи информации по каналу с шумом.

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

 

         k-разрядным двоичным словам можно поставить в соответствие 2k возможных значений из алфавита источника, которым соответствует 2k кодовых слов на выходе кодера. Такое множество 2k кодовых слов называется блочным кодом.

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

 

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

 

         Блочные коды удобны в тех случаях, когда исходные данные по своей природе сгруппированы в блоки или массивы.

 

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

   

 

3.2  Линейные блочные коды

 

         Для блочного кода с 2k кодовыми словами длиной n символов, если он не обладает специальной структурой, аппарат кодирования/ декодирования оказывается очень сложным. Одним из условий практической реализуемости блочного кода является условие его линейности.

Определение.  Блочный код длиной n символов, представляющий множество 2k кодовых слов, называется линейным (k, n)-кодом при условии, что все его кодовые слова образуют k-мерное подпространство векторного пространства n-последовательностей двоичного поля GF(2).

         Иными словами, двоичный код является линейным, если поразрядная сумма по модулю 2 (mod 2)[i] двух кодовых слов также является кодовым словом данного кода.

         Желательным качеством линейных блочных кодов является систематичность. Систематический код имеет неизменную информационную часть длиной k символов и избыточную (проверочную) часть длиной n-k символов (рис. 3.1).

 

 

3.2.1  Основные понятия двоичной арифметики

 

         Полем называется множество математических объектов, для которых определены операции сложения, вычитания, умножения и деления.

Возьмем простейшее поле из двух элементов 0 и 1. Определим для него операции сложения и умножения следующим образом:

 

0+0=0,

0+1=1,

1+0=1,

1+1=0;

 

0*0=0,

0*1=0,

1*0=0,

1*1=1.

 

 

 

 

 

Определенные таким образом операции сложения и умножения называются сложением по модулю 2 (mod 2) и умножением по модулю 2.

Из равенства 1+1=0 следует, что -1=1 и 1+1=1-1, а из равенства 1*1=1 – что 1:1=1.

         Алфавит из двух символов 0 и 1 вместе с операциями сложения и умножения по mod 2 называется двоичным полем GF(2). К полю GF(2) применимы все методы линейной алгебры, в том числе матричные операции.

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

 

3.3  Код с проверкой на четность

 

         Самый простой линейный блочный код – это (n-1, n) - код с контролем четности. Данный код, в частности, широко используется в модемах.

Кодирование заключается в добавлении к каждому байту 9-го бита таким образом, чтобы дополнить количество единиц в байте до заранее выбранного для кода четного (even) или нечетного (odd) значения.

 

Например, информационная последовательность (101), тогда кодовой последовательностью будет (1010), где проверочный символ формируется путем суммирования по mod 2 символов информационной последовательности. Заметим, что если число единиц в информационной последовательности четно, то результатом суммирования по mod 2 будет 0, если нечетно – то 1, т.е. проверочный символ дополняет кодовую последовательность так, чтобы количество единиц в ней было четным.

        

Математически схему кодирования с проверкой на четность можно описать следующим образом:

 

Е(m1, ..., mk)= m1, ..., mk, mk+1, где

 

Таким образом, количество единиц в принятой последовательности должно быть четным, т. е. .

Схему декодирования можно представить как

 

 

 

 

Введем определение двоичного симметричного канала, для которого ошибки в битах равновероятны и независимы. Схематически двоичный симметричный канал представлен на рис. 3.2, где р – вероятность безошибочной передачи бита сообщения; q=1-p – вероятность ошибочной передачи.

 

 

 

 

 

 

Рисунок 3.2

 

Для такой схемы передачи данных вероятность того, что в n-позиционном коде произойдет только одна ошибка, составит .

         В общем случае вероятность передачи n битов с k ошибками определяется формулой Бернулли

 

,                                       (3.1)

                 

где - число сочетаний из n по k.

        

Заметим, что код с проверкой четности не обнаруживает ошибки кратности 2, так как если в переданной последовательности произошло 2, 4 и т.д. ошибки, независимо в какой позиции, то общее число единиц в принятой последовательности будет четным, и ошибки обнаружены не будут. Однако вероятность двойной ошибки значительно меньше одиночной. Покажем это на простом примере.

 

Пример.  Проверка четности при k=2 реализуется следующим кодом: 00000, 01011, 10101, 11110.

 

Обозначим как р – вероятность правильной передачи, q – вероятность ошибочной передачи бита сообщения.

Тогда вероятность возникновения хотя бы одной ошибки в кодовой последовательности длиной 3 бита равна q3+3pq2+3p2q. Из них не будут обнаружены ошибки в двух битах, не изменяющих четности, вероятность которых Pош=3pq2.

Вероятность ошибочной передачи сообщения из двух битов без использования контроля четности составляет Pош=q2+2pq.

При использовании достаточно надежного канала передачи данных, т. е. при q <<1, 3pq2 <<q2+2pq, что говорит о целесообразности использования помехоустойчивого кодирования с обнаружением однократных ошибок.

          

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

 

 

 

13