Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 78

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 72 73 74 75 76 77 < 78 > 79 80 81 82 83 84 .. 104 >> Следующая

0,60 -0,35- 0,15 -р4
дает код 001. Таким образом, мы получаем следующую схему;
ал — 1 а2 — 01, а3 — 000, щ — 001,
что совпадает со схемой 2" на с. 276. Значит, код определяемый 2", имеет минимальную избыточность.
Осуществляя редукцию, на каждом шаге производится упорядочение вероятностей по их величине. Это упорядочение оказывается не всегда однозначным, так как возможно появление вероятностей, имеющих одинаковую величину.
Пример 13. Пусть г = 8, д — 4 и рй = 0,22, р2 = 0,20, /?3=0Д4, />4= 0,11, рь= 0,10, рв = 0,09, />7 = 0,08, />е = 0,06. Возьмем 0 = (0, 1, 2, 3). Редукцию можно осуществить
здесь двумя способами:
—> 0,44“
С-] сч о' II н о. 0,22 0,22
р2 = 0,20 0,20 0,20
->0,14 0Л14_
Рз = 0,14"
/>4 = 0,11 0,11
Чз «е ІІ О о 0,10
= 0,00 0,09.
Рі = 0,08 і Рн = одосИ
->0,44~
р1 = 0,22 0,22 0,22
ра = 0,20 0,20 0,20
т—1 О 1! сС 0,14 0,14_
->0,14"
И о 0,11 _
Ръ = о»ю 0,10
рв =» 0,09 0,09
р1 = 0,08 ч____
р8 = 0,06_
Отсюда получаем две схемы алфавитного кодирования (нумеруя члены в скобках сверху вниз числами 0, 1, 2, 3)
йі — 1 йі — 1
о г 2 о>2 2-
й з — 00 а3 — 3
«*-01 (Г) а* -01 С27/)
аъ — 02 а5 — 02
а.6 — 03 й6 — 03
й7 — 30 ат — 000
а8 — 31 а8 — 001
Кодовое дерево для 2' совпадает с деревом на рйс. 14.
В заключение рассмотрим построение кодов с минимальной избыточностью для случая, когда вероятности ри * .рг — произвольны, > ... > рг. Если число нулевых вероятностей больше единицы, Т. е. Рго>0 и
Ргй+1 “ * * • “ Р? == Г Г0 ^ I
то сначала находят решение для (г0+ 1)-буквенного входного алфавита и вероятностей ри ..., рТ(), Рг0+1 (Рг0 +1= 0). Пусть В1% ..ЯГ((, -6г0-Ь1 — элементарные коды для кода с минимальной избыточностью. Затем отбрасывают оло-ментарный код Вг ы и для букв Яг0ы, берут в
качестве элементарных кодов слова вида
?#г0+1 — вг^Ь1в „
• • • • I * 9 Л *
Вт - ВГй+1&г\
где = ,.. = 1(В(г}) и все слова В^0+1^ ( ., .г В(г)
различны. Очевидно, что построенный код имеет минимальную избыточность и удовлетворяет свойству префикса.
§ 5. Самокорректирующиеся коды
Здесь мы рассматриваем один частный случай равномерного кодирования.
Пусть §? = (О, 1) — алфавит, содержащий два символа. Пуеть далее {Ли А2, .АА—множество всех слов А = *= &!... а™ в алфавите 9?, имеющих фиксированную длину т. (Здесь я — 2т.)
Предположим, что в канале связи действует источник помех, который в словах из {А^ АА, имеющих длину
примерно т, может вызывать ошибки не более чем в р символах. Это значит, что двоичпая последовательность, полученная на выходе канала, отличается от двоичной последовательности, поступившей на вход этого канала, не более чем в р позициях. Совершенно ясно, что, если передавать исходное сообщение оц ... ос,„ (без предварительного кодирования), то на выходе канала невозможно будет установить, какое сообщение фактически было передано. В связи с этим возникает вопрос, нельзя ли осуществить кодирование слов А из множества {Аи ../1л), т. е. слов вида а!... ат, словами ^ длины I так, чтобы
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
289
по коду.Р??( полученному на выходе канала при передаче кода р! р(, можно было однозначно восстановить
этот код, и, значит, исходное сообщение <*1... ат? Коды, обладающие данным свойством, будем называть самокорректирующимися кодами относительно рассматриваемого источника помех.
Легко видеть, что существует тривиальное решение задачи. Мы проследим это на простейшем источиике помех, для которого р =* 1, т. е. для которого возможно только искажение 0 1 или 1 -? 0. Искомый самокорректи-
рующийся код получается путем утроения символов исходного кода
с^а-г... ат — •.. атата,т,
Б самом деле, если при передаче этого кода произошла ошибка, то в некоторой группе а(а<а< искажен ров по один символ, а остальные группы передапы без ошибок. Это позволяет методом «голосования» осуществить коррекцию ошибки и восстановить код ... сстоиат), а значит
и исходное сообщение (а.1 ., .ат).
Тривиальное решение не является корректным, так как длина кода здесь равна I = 3т н мы приходим к кодам, для которых данный источник помех может вызывать большее число ошибок, чем р, и тогда однозначно восстановить исходное сообщение не всегда будет возможно.
Корректное построение самокорректирующихся кодов было осуществлено Хэммингом [40]. Им подробно был разобран случай р = 1, к изложению которого мы и перейдем.
Сообщения кодируются наборами р!... где
I — длина кода и / = т + к. Очевидно, что при наличии данного источника помех возможны следующие варианты получения кодов на выходе (см. рис. 15).
Следовательно, число вариантов равно I + 1. Для того чтобы дополнительных разрядов в коде р!... хватало для кодировки перечисленных 14-1 случаев передачи кода, необходимо, чтобы
2к>1+1 или 2т<2У(Г + 1).
Из этих соображений выберем I как наименьшее целое число, удовлетворяющее псравепству
2м *? 27^+ 1).
19 с. В. Яблонский
1, IV» 1ШҐИ/1 ПиДИГиВАШШ
Дальнейшие построения будут состоять из трех этапов.
I. Построение кодов Хэмминга (описание алгоритма кодирования). Разобьем отрезок натуральных чисел (1, 2, I) на к последовательностей следующим образом: пусть У — произвольное натуральное число
Предыдущая << 1 .. 72 73 74 75 76 77 < 78 > 79 80 81 82 83 84 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed