Задача кодирования

Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 25.02.2009
Размер файла 212,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

- кратность ошибки t меньше половины величины кодового расстояния d, т.е. t Ј [(d-1)/2]

- кратность ошибки t меньше величины кодового расстояния d, т.е. t < d

- кратность ошибки t больше величины кодового расстояния d, t > dі

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

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

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

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

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

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

5. Процедуры кодирования и декодирования кода содержат, в основном, операции по модулю 2.

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

1.4.3 Код Шеннона

Оптимальным кодом можно определить тот, в котором каждый двоичный символ будет передавать максимальную информацию. В силу формул Хартли и Шеннона максимум энтропии достигается при равновероятных событиях, следовательно, двоичный код будет оптимальным, если в закодированном сообщении символы 0 и 1 будут встречаться одинаково часто.[8]

Рассмотрим в качестве примера оптимальное двоичное кодирование букв русского алфавита вместе с символом пробела «-». Полагаем, что известны вероятности появления в сообщении символов русского алфавита, например, приведенные в таблице 3.

Таблица 3.Частота букв русского языка (предположение)

К. Шеннон и Р. Фано независимо предложили в 1948-1949 гг. способ построения кода, основанный на выполнении условия равной вероятности символов 0 и 1 в закодированном сообщении. [10]

Все кодируемые символы (буквы) разделяются на две группы так, что сумма вероятностей символов в первой группе равна сумме вероятностей символов второй группы (то есть вероятность того, что в сообщении встретится символ из первой группы, равна вероятности того, что в сообщении встретится символ из второй группы).

Для символов первой группы значение первого разряда кода присваивается равным «0», для символов второй группы - равными «1».

Далее каждая группа разделяется на две подгруппы, так чтобы суммы вероятностей знаков в каждой подгруппе были равны. Для символов первой подгруппы каждой группы значение второго разряда кода присваивается равным «0», для символов второй подгруппы каждой группы - «1». Такой процесс разбиения символов на группы и кодирования продолжается до тех пор, пока в подгруппах не остается по одному символу.

Пример кодирования символов русского алфавита приведен в табл. 4

Таблица 4. Пример кодирования букв русского алфавита с помощью кода Шеннна-Фано.

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

Вместе с тем процедура построения кода Шеннона-Фано удовлетворяет критерию различимости Фано. Код является префиксным и не требует специального символа, отделяющего буквы друг от друга для однозначного него декодирование двоичного сообщения.

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

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

2.Практическая реализация задачи кодирования

2.1 Пример к первой теореме Шеннона

Задача эффективного кодирования описывается триадой:

X = {X 4i 0} - кодирующее устройство - В.

Здесь Х, В - соответственно входной и выходной алфавит. Под множеством х 4i 0 можно понимать любые знаки (буквы, слова, предложения). В - множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления 2 ( например 2, m = 2 2) . Кодирующее устройство сопоставляет каждому сообщению x 4i 0 из Х кодовую комбинацию, составленную из n 4i символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.

Для решения данной задачи должна быть известна вероятность P 4i появления сообщения x 4i 0, которому соответствует определенное количество символов n 4i алфавита B. Тогда математическое ожидание количества символов из B определится следующим образом: n 4ср = n 4i P 4i (средняя величина).

Этому среднему количеству символов алфавита В соответствует максимальная энтропия H 4max = n 4ср log m. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H 4max >= H(x) 4, или n 4ср log m >= - P 4i log P 4i . В этом случае закодированное сообщение имеет избыточность

n 4ср >= H(x)/log m, n 4min = H(x)/log 4 m.

Коэффициент избыточности

Ku = (H 4max - H(x))/H 4max = (n 4ср - n 4min )/n 4ср .

Составим соответствующую таблицу. Имеем:

n 4min = H(x)/log 2 = 2.85, Ku = (2.92 - 2.85)/2.92 = 0.024,

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

Таблица 2.1 Пример к первой теореме Шеннона

N

0,1

P(x,4i)

(x,4i)

код

n,4i

n,4i p,4i

Px 4i log Px 4i

1

2

3

4

5

6

7

8

0.19

0.16

0.16

0.15

0.12

0.11

0.09

0.02

X1

X2

X3

X4

X5

X5

X7

X8

10

001

011

100

101

111

1011

1001

2

3

3

3

3

3

4

4

0.38

0.48

0.48

0.45

0.36

0.33

0.36

0.08

-4.5522

-4.2301

-4.2301

-4.1054

-3.6706

-3.5028

-3.1265

-3.1288

Px 41 0=1,0

=2.92

H(x)=2.85

2.2 Пример построения кода Шеннона

В таблице 2.2 приведены промежуточные вычисления и результат построения кода Шеннона. Средняя длина кодовых слов l = 2,95. В данном случае избыточность кода Шеннона на 0,5 бита больше, чем избыточность кода Хаффмена. Из этого рисунка понятно, почему код неэффективен. Кодовые слова для букв b , d , e , f могут быть укорочены на 1 бит без потери свойства однозначной декодируемости.

Таблица 2.2 Построение кода Шеннона

Буква

Вероятность p m

Кумулятивная вероятность q m

Длина кодо- вого слова l m

Двоичная запись [ q]2

Кодовое слово c m

a

0,35

0,00

2

0,00…

00

b

0,20

0,35

3

0,0101…

010

c

0,15

0,55

3

0,10001…

100

d

0,10

0,70

4

0,10110…

1011

e

0,10

0,80

4

0,11001…

1100

f

0,10

0,90

4

0,11100…

1110

Докажем однозначную декодируемость кода Шеннона. Для этого выберем сообщения с номерами i и j , i < j . Кодовое слово ci для i заведомо короче, чем слово cj для j , поэтому достаточно доказать, что эти слова отличаются в одном из первых li символов.

Рассмотрим разность qj ? qi =У pk ? У pk =У pk ? pi

Вспомним, что длина слова и его вероятность связаны соотношением

li = [? log pi ]? ? log pi .

Поэтому pi ?2-li .

С учетом этого неравенства

q j ? q i ? 2-li

В двоичной записи числа в правой части мы имеем после запятой li ?1 нулей и единицу в позиции с номером li. Это означает, что по меньшей мере в одном из li разрядов слова ci и cj отличаются и, следовательно, ci не является префиксом для cj. Поскольку это верно для любой пары слов, то код является префиксным.

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

l ? H +1.

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

2.3 Пример Кода Шеннона

Допустим, нужно закодировать некоторое сообщение: AABCDAABC

Имеем :

A - 5 5/10 = 0.5

B - 2 2/10 = 0.2

C - 2 2/10 = 0.2

D - 1 1/10 = 0.1

Длина всего сообщения 10 (Вычисляется веpоятность встpечаемости каждого символа и pасполагаем их в столбик в поpядке yбывания веpоятностей)

После этого стpоим кодовые комбинации пpостым методом. Делим столбик с веpоятностями таким обpазмо, чтобы сyмма веpоятностей веpхней части pавнялась пpиблизительно сyмме веpоятностей нижней части

0.5 - пеpвая часть = 0.5

-----

0.2 \

0.2 | - втоpая часть = 0.5

0.1 /

Напpитив веpоятностей веpхней части пpоставляем нyли, напpотив нижней - еденицы. В нашем пpимеpе полyчим.

0.5 0

0.2 1

0.2 1

0.1 1

Пpделываем потом то же с pазделенными частями. В конце-концов пpидем к томy, что делить больше нечего.

А 0.5 0

B 0.2 10

C 0.2 110

D 0.1 111

Итого - AABCDAABC = 0 0 10 110 111 0 0 10 110

Пpичем закодиpованное сообщение (это видно) не может быть pаскодиpовано несколькими способами, хотя длина кодов символов отличается. Чтобы пpочитать закодиpованное сообщение стpоится бинаpное деpево. В нашем слyчае оно бyдет такое.

()

/ \

0(A) 1

/ \

0(B) 1

/ \

0(C) 1(D)

Вот еще пpимеp составления кодовых комбинаций по веpоятносям:

0.3 00

0.25 01

--------------- (пеpвое деление)

0.1 100

0.1 101

------------- (втоpое деление)

0.1 1100

0.05 1101

----------- (тpетье деление)

0.05 1110

0.05 1111

2.4 Пример кодирования и декодирования методом Шеннона-Фано

С помощью табл. 4 можно закодировать и декодировать любое сообщение. В виде примера запишем двоичным кодом фразу: "Теория информаций"

0 111 010000 11 01 000 11 011 11 0000

01101000111111 111 00110 100

11 0000 10111111 10101100110

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

10011100110011001001111010000

1011100111001001101010000110101

010110000110110110

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

Заключение

В ходе курсовой работы была рассмотрена задача кодирования, которая включает в себя:

1.Обеспечение экономичности передачи информации посредством устранения избыточности.

2. Обеспечение надежности (помехоустойчивости) передачи информации

3.Согласование скорости передачи информации с пропускной способностью канала

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

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

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

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


Подобные документы

  • Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.

    контрольная работа [94,6 K], добавлен 04.05.2015

  • Разработка алгоритма и программы кодирования и декодирования данных кодом Рида-Малера. Понятие избыточных кодов, их применение. Корелляционный код. Особенности построения простых помехоустойчивых кодов Рида-Маллера. Рассмотрение частных случаев.

    курсовая работа [31,9 K], добавлен 09.03.2009

  • Изучение сущности циклических кодов - семейства помехоустойчивых кодов, включающих в себя одну из разновидностей кодов Хэмминга. Основные понятия и определения. Методы построения порождающей матрицы циклического кода. Понятие открытой системы. Модель OSI.

    контрольная работа [99,5 K], добавлен 25.01.2011

  • Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано.

    курсовая работа [59,4 K], добавлен 17.04.2009

  • Циклические коды как подкласс (подмножество) линейных кодов, пошаговый алгоритм и варианты их кодирования и декодирования. Методика построения интерфейса отладочного модуля. Элементарный план и элементы отладки декодирующего модуля циклических кодов.

    лабораторная работа [133,8 K], добавлен 06.07.2009

  • Анализ методов сверточного кодирования. Понятие канала связи и корректирующих кодов, характеристика автомата типа Мура. Особенности сверточного декодирования Витерби. Сущность разработки программного обеспечения системы кодирования сверточным кодом.

    дипломная работа [4,9 M], добавлен 11.03.2012

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

    доклад [12,6 K], добавлен 11.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.