Программная модель помехоустойчивого кодирования

Программная модель помехоустойчивого кодирования

Содержание 
 

Введение……………………………………………………………………………3

Глава 1. 

1.1 Основные принципы. Типы кодов …………………………………………...5

     1.2 Линейные блочные коды………………………………………………..7 

     1.2.1 Код с проверкой на четность……………………………………….9

     1.2.2 Порождающая матрица линейного блочного кода …………………12

     1.2.3 Синдром и обнаружение ошибок ……………………………………16

     1.2.4 Синдромное декодирование линейных блочных кодов …………18

     1.2.5 Вес и расстояние Хемминга. Способность кодов обнаруживать  и исправлять ошибки ………………………………………………………………21

     1.3 Циклические коды……………………………………………………..26

     1.3.1 Кодирование с использованием циклических кодов……………..27

     1.3.2 Вычисление  синдрома  и исправление  ошибок  в циклических кодах………………………………………………………………………………32

     1.3.3 Неалгебраические методы декодирования циклических кодов …..34

     1.4 Сверточные коды……………………………………………………..38

     1.4.1 Кодирование с использованием сверточных кодов ………………..39

     1.4.2 Синдромное декодирование сверточных кодов………………….43

     1.4.3 Декодирование сверточных кодов. Алгоритм  Витерби …………46

Глава 2

     2.1 Коды Шеннона – Фано (Теоритическая часть)……………………..50

     2.2 Описание Кода Шеннона – Фано……………………………………55

Заключение  ……………………………………………………………………….56

Литература………………………………………………………………………..57

Приложение1……………………………………………………………………..58 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

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

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

    Возможность использования кодирования для  уменьшения числа ошибок в канале была теоретически показана К. Шенноном в 1948 году в его работе "Математическая теория связи".  В ней было сделано утверждение, что если скорость создания источником сообщений (производительность источника) не превосходит некоторой величины, называемой пропускной способностью канала, то при соответствующем кодировании и декодировании можно свести вероятность ошибок в канале к нулю.

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

    Цель  исследования: на основе теоретического анализа изучить механизм действия помехоустойчивого кодирования.

    Объект исследования: код Шеннона – Фано.

    В соответствии с целью работы были определены следующие задачи исследования:

    1. Изучить основные типы кодов  помехоустойчивого кодирования;

    2. Исследовать один из выбранных кодов (код Шеннона - Фано)

    3. Реализовать код Шеннона –  Фано на языке программирования  Pascal.

    Исследование  осуществлялось с помощью следующих методов: научный анализ специальной литературы и обобщение данных по основам помехоустойчивого кодирования.

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

    Глава 1

     1.1 Основные принципы. Типы кодов

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

    Первое  − использование избыточности. Закодированные последовательности всегда содержат дополнительные, или избыточные, символы. Количество символов в кодовой последовательности Y  всегда больше, чем необходимо  для однозначного представления любого сообщения λ_i из алфавита.  

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

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

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

    Кодер канала преобразует блоки-сообщения X в более длинные двоичные последовательности  Y, состоящие из n символов и называемые кодовыми словами. Символы (n-k), добавляемые к каждому блоку-сообщению кодером, называются избыточными. Они не несут никакой дополнительной информации, и их функция состоит в обеспечении возможности обнаруживать (или исправлять) ошибки, возникающие в процессе передачи. [2]

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

    Такое множество 2^k кодовых слов называется блочным кодом.

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

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

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

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

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

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

    Одним из условий реализуемости блочных  кодов при больших k является условие их линейности.

    Что такое линейный код?

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

       Если сказать проще, то  двоичный код является линейным, если сумма по модулю 2 ( mod2 ) двух кодовых слов также является кодовым словом этого кода.

    Работая с двоичными кодами, мы постоянно  будем сталкиваться с элементами двоичной арифметики, поэтому определим основные понятия.

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

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

    0+0=0,            0× 0=0;  
       0+1=1,            0× 1=0; 
       1+0=1,            1× 0=0; 
       1+1=0,            1× 1=1.

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

    Отметим, что из равенства 1+1 = 0 следует, что -1 = 1 и, соответственно, 1+1=1-1, а из равенства 1×1=1  − что 1:1=1. 

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

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

    Желательным качеством линейных блочных кодов  является систематичность.

    Систематический код имеет формат, изображенный на рис. 1.1, то есть содержит неизменную информационную часть длиной k символов и избыточную (проверочную)  длиной  n – k символов.

Рис. 1.1

    Блочный код, обладающий свойствами линейности и систематичности, называется линейным блочным систематическим (n, k)-кодом.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

    Самым простым линейным блочным кодом  является (n,n-1)-код, построенный с помощью одной общей проверки на четность. Например, кодовое слово (4,3)-кода можно записать в виде вектора-столбца:

                              = ( m₀, m₁, m₂, m₀+m₁+m₂ ),                                  (1.1) 

    где   m_i  -  символы информационной последовательности, принимающие значения 0 и 1, а суммирование производится по модулю 2 ( mod2 ).

    Поясним основную идею проверки на четность.

    Пусть информационная последовательность источника  имеет вид

                                m  = ( 1 0 1 ).         (1.2)

    Тогда соответствующая ей кодовая последовательность будет выглядеть следующим образом :

                           U = ( U₀, U₁, U₂, U₃ ) = ( 1 0 1 0 ), (1.3)

    где проверочный символ U₃ формируется путем суммирования по mod2 символов информационной последовательности   m :

                             U₃ = m₀ +  m₁ + m₂ .                                                         (1.4)

    Нетрудно  заметить, что если число единиц в последовательности  m четно, то результатом суммирования будет 0, если нечетно — 1, то есть проверочный символ дополняет кодовую последовательность таким образом, чтобы количество единиц в ней было четным. [6]

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

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

                            P₁ = n× P_ош × (1- P_ош)^n-1                                                                            (1.5)

    (то  есть в одном бите ошибка  есть, а во всех остальных  n - 1  битах ошибки нет).

    Вероятность того, что произойдет две ошибки, определяется уже числом возможных  сочетаний ошибок по две (в двух произвольных битах ошибка есть, а во всех остальных n - 2  битах ошибки нет):

                        P₂ = C_n² × P_ош × (1- P_ош)^n-2  ,                                                                         (1.6)

    и аналогично  для ошибок более  высокой кратности.

    Если  считать, что вероятность ошибки на символ принятой последовательности P_ош достаточно мала (P_ош<<1), а в противном случае передача информации не имеет смысла, то вероятность выпадения ровно l  ошибок составит  P_l @ P_ош^l. 

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

    Если  при передаче рассматриваемого (4,3)-кода произошла одна ошибка, причем неважно, в какой его позиции, то общее число единиц в принятой последовательности  r уже не будет четным.

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

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

    На  основании общей идеи проверки на четность и проверочного уравнения (1.4)  легко организовать схему  кодирования - декодирования для  произвольного кода с простой  проверкой на четность.

    Схема кодирования может выглядеть  следующим образом   (рис. 1.2):  
 
 

Рис. 1.2

    Декодирующее  устройство для кода с проверкой  на четность изображено на  рис. 1.3.

    Рис. 1.3 

    Декодер, как это видно из рис. 1.3, проверяет на четность общее число единиц в принятой последовательности и выдает на своем выходе нуль или единицу в зависимости от того, выполнилась проверка или нет.[17]

    Отметим следующий момент. Если посимвольно  сложить два кодовых слова, принадлежащих рассматриваемому (4, 3)-коду:

          a  = ( a₀, a₁, a₂, a₀ + a₁ + a₂ ),  и  b  = ( b₀, b₁, b₂, b₀ + b₁ + b₂ ),            (1.7)

то получим

    с = ( a₀+b₀, a₁+b₁, a₂+b₂, a₀+b₀+a₁+b₁+a₂+b₂) = ( c₀, c₁, c₂, c₀+c₁+c₂ ),        (1.8)

то  есть проверочный символ в новом слове с определяется по тому же правилу, что и в слагаемых. Поэтому с  также является кодовым словом данного кода.

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

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

    1.2.2 Порождающая матрица линейного блочного кода 

    Только  что в качестве примера были рассмотрены  два простейших корректирующих кода  - код с простой проверкой на четность, позволяющий обнаруживать однократную ошибку в принятой последовательности, и блочный итеративный код, исправляющий одну ошибку с помощью набора проверок на четность по строкам и столбцам таблицы.  Однако  формальное правило, по которому осуществляется кодирование, то есть преобразование информационной последовательности в кодовое слово, по-настоящему еще не определено.  Так как же задаются блочные коды?[11]

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

                       Таблица 1.2

      Такой способ описания кодов, кстати, применим для любых, а  не только линейных кодов. Однако при больших k  размер кодовой таблицы оказывается слишком большим, чтобы им пользоваться на практике (для кода с простой проверкой на четность двухбайтового слова размер таблицы составит  ~ 2⁵ * 2¹⁶  = 2000000 двоичных символов).

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

U₀ = m₀,

U₁ = m₁,          (1.9)

U₂ = m₂,     

U₃ = m₀  + m₁ + m₂.

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