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

Автор работы: Пользователь скрыл имя, 15 Декабря 2010 в 13:39, курсовая работа

Описание

Цель исследования: на основе теоретического анализа изучить механизм действия помехоустойчивого кодирования.
Объект исследования: код Шеннона – Фано.
В соответствии с целью работы были определены следующие задачи исследования:
1. Изучить основные типы кодов помехоустойчивого кодирования;
2. Исследовать один из выбранных кодов (код Шеннона - Фано)
3. Реализовать код Шеннона – Фано на языке программирования Pascal.

Содержание

Введение……………………………………………………………………………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

Работа состоит из  1 файл

курсовая.doc

— 877.00 Кб (Скачать документ)

          Доказано, что расстояние между нулевым  кодовым словом и одним из кодовых  слов, входящих в порождающую матрицу (строки порождающей матрицы линейного  блочного кода сами являются кодовыми словами, по определению), равно dmin. Но расстояние от любого кодового слова до нулевого равно весу Хемминга этого слова. Тогда dmin  равно минимальному весу Хемминга  для всех строк порождающей матрицы кода .

          Если  при передаче кодового слова по каналу связи в нем произошла одиночная ошибка, то расстояние Хемминга между переданным словом U и принятым вектором  r будет равно единице. Если при этом одно кодовое слово не перешло в другое (а при dmin > 1 и при одиночной ошибке это невозможно), то ошибка будет обнаружена при декодировании.

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

          Но  ошибки могут иметь кратность  и большую, чем dmin- 1, и тогда они останутся необнаруженными.

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

          Пусть вероятность ошибки в канале связи равна Pош. Тогда вероятность того, что при передаче последовательности длины n  в ней произойдет одна ошибка, равна

                                Р1 = n Pош × ( 1- Рош)n-1,                                                      (1.36)

      соответственно, вероятность l-кратной ошибки  - 

                      Pl =Cnl Pошl × ( 1- Pош)n-l,                                                       (1.37)

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

            По каналу связи передаются кодовые слова с различными весами Хемминга. Положим, что ai — число слов с весом i в данном коде (всего слов в коде длиной n  -  ).

            А теперь определим, что такое необнаруживаемая ошибка. Обнаружение ошибки производится путем вычисления синдрома принятой последовательности. Если принятая последовательность не является кодовым словом ( тогда синдром не равен нулю), то считается, что ошибка есть. Если же синдром равен нулю, то полагаем, что ошибки нет (принятая последовательность является кодовым словом). Но тем ли, которое передавалось?  Или же в результате действия ошибок переданное кодовое слово перешло в другое кодовое слово данного кода:

                                             r  = U  + е =  V,                                                       (1.38)

      то  есть сумма  переданного кодового слова U и вектора ошибки е даст новое кодовое слово V ? В этом случае, естественно, ошибка обнаружена быть не может.[16]

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

            Вероятность того, что вектор е совпадает с кодовым словом, имеющим вес i , равна

                                          Pi = Pошi × (1- Рош)n-i .                                                    (1.39)

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

                             .                                                (1.40)

            Пример: рассматриваемый нами (7,4)-код содержит по семь кодовых слов с весами w = 3 и w = 4 и одно кодовое слово с весом w = 7, тогда

                      (1.41)

      или,  при Рош = 10 -3, Р(Е) @ 7 × 10 -9.

            Другими словами, если  по  каналу  передается информация со скоростью V = 1кбит/с и в канале в среднем каждую секунду будет происходить искажение одного символа, то в среднем семь принятых слов на 109 переданных будут проходить через декодер без обнаружения ошибки (одна необнаруживаемая ошибка за  270 часов).

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

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

          Рассмотрим  пример, приведенный на рис. 1.9. Пусть  U и V представляют пару кодовых слов кода с кодовым расстоянием d , равным минимальному — d min для данного кода.

    

 

                Рис. 1.9

          Предположим, передано кодовое слово U, в канале произошла одиночная ошибка  и принят вектор а (не принадлежащий коду).

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

          Таковым в данном случае будет U, следовательно, ошибка будет устранена.

          Представим  теперь, что произошло две ошибки и принят вектор b.

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

          Продолжив рассуждения для dmin = 4, dmin = 5 и т.д., нетрудно сделать вывод, что ошибки будут устранены, если их кратность l не превышает величины

                l< INT (( dmin – 1 )/2) ,           (1.41)

      где  INT (X) — целая часть Х.

          Так, используемый нами в качестве примера  (7,4)-код имеет dmin = 3 и, следовательно,  позволяет исправлять лишь одиночные ошибки:

                                l = INT (( dmin – 1 )/2)=INT((3-1)/2)=1 .                             (1.42)

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

            А теперь определим  вероятность того, что возникшая  в процессе передачи ошибка не будет все  же  исправлена при  декодировании.

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

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

                             Рош     =  P + P + P +... + P ,                                             (1.43)

      Где Р1—вероятность того, что в r присутствует одиночная ошибка;  
      Р2—вероятность того, что ошибка двойная и т.д.;  
      Рn  — вероятность того, что все n символов искажены.

          Определим вероятность ошибок заданной кратности:

      Р1 = Вер{ошибка в 1-й позиции ИЛИ ошибка во 2-й позиции ..ИЛИ в n-й позиции} = = Рош(1- Рош)n-1 + Рош(1- Рош)n-1 +...Рош(1- Рош)n-1 =  п × Рош(1- Рош)n-;         (1.44)

      Р2 = Вер{ошибка в 1-й И во 2-й позиции ИЛИ ошибка во 2-й И в 3-й позиции} =

        = P2ош(1-Рош)n-2 +...Р2ош(1- Рош) n-2 = Р2ош(1- Рош) n-2.                              (1.45)

            Аналогичным образом

                         Р3 = Р3ош(1- Рош)n-3   и т.д.                                                       (1.46)

          Декодер, как мы показали, исправляет все  ошибки, кратность которых не превышает

                              ,                                              (1.47)

      то  есть все ошибки кратности J £ l   будут исправлены.[15]

          Тогда ошибки декодирования - это ошибки с  кратностью, большей кратности исправляемых ошибок  l, и их вероятность

            .                                     (1.48)

      Для (7,4)-кода Хемминга минимальное расстояние dmin = 3, т.е. l = 1. Следовательно, ошибки кратности 2  и более исправлены не будут и

               .                                (1.49)

      Если  Рош<< 1, можно считать (1- Рош) » 1 и, кроме того, Р3ош<< Р2ош. Тогда

                   .                                          (1.50)

          Так, например, при вероятности ошибки в канале Рош = 10 -3 вероятность неисправления ошибки Р(N) » 2 ×10 -5, то есть  при такой вероятности ошибок в канале кодирование (7.4)-кодом позволяет снизить вероятность оставшихся неисправленными ошибок примерно в пятьдесят раз

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