Новиков Ф.А. Дискретная математика для программистов (860615), страница 41
Текст из файла (страница 41)
. ( e - 1)Sb : = 0 { сумма элементов первой части }for г from 6 to е — 1 doSb : = Sb + P[i] { вначале все, кроме последнего }end forSe: — P[e] { сумма элементов второй части }тп: = е { начинаем искать медиану с конца }1Роберт М. Фано (р. 1917).Еi=m+lp[i6.2. Кодирование с минимальной избыточностью217repeat\d: = Sb — 5 е | { разность сумм первой и второй частей }т : = т — 1 { сдвигаем границу медианы вниз }Sb'.
= Sb- Р[т}\ Se: — Se + Р[т] { перевычисляем суммы }until \Sb - Se| > dreturn mПри каждом удлинении кодов в одной части коды удлиняютсянулями, а в другой — единицами. Таким образом, коды одной части пе могутбыть префиксами другой. Удлинение кода закапчивается тогда и только тогда,когда длина части равна 1, то есть остается единственный код. Таким образом,схема по построению префиксная, а потому разделимая.ПОБОСНОВАНИЕПример Коды, построенные алгоритмом Фано для заданного распределениявероятностей (п = 7).Pi0,200,200,190,120,110,090,09C[i]kpih0001001110010111011123333330,400,600,570,360,330,270,272,80UP)6.2.4.
Оптимальное кодированиеОптимальные схемы алфавитного кодирования обладают определёнными структурными свойствами, устаналиваемыми в следующих леммах. Нарушение этихсвойств для какой-либо схемы означает, что схема не оптимальна.Пусть а = (а* —> А)Г= i — схема оптимального кодирования для распределения вероятностей Р = р\ ^ ... ^ рп > 0. Тогда еслирг > pj, то U < lj.ЛЕММА1О Т противного.
Пусть i < j, pi > pj и k > lj. Тогда рассмотримсхему а' = {ai —> j3\,...,сч —» Pj,... ,a,jPi,... ,an —» pn}. Имеем:- la> == (pik + pjlj) - (pilj -(- pjk) = (pi - Pj)(U - lj) > 0, что противоречит тому, чтосхема а — оптимальна.•ДОКАЗАТЕЛЬСТВОТаким образом, пе ограничивая общности, можно считать, что li ^ . . . ^ 1п.ЗАМЕЧАНИЕФактически, лемма 1 повторяет для вероятностей то, что было обнаружено для частотв подразделе 6.2.1.218Глава 6.
Кодирование 218ЛЕММА 2Если а = (А* —<• А ) ™ = 1 — схема оптимального префиксного кодированиядля распределения вероятностей Р = р\ ^ ... ^ рп > 0, то среди элементарных кодов имеются два кода максимальной длины, которые различаются только впоследнем разряде.ДОКАЗАТЕЛЬСТВОП О предыдущей лемме кодовые слова максимальной длины являются последними в схеме. Далее от противного.[ 1 ] Пусть кодовое слово максимальной длины одно и имеет вид рп = РЪ, где6 = 0 V 6 = 1.
Имеем: Vг е 1..гг - 1 (U ^ |/3|). Так как схема префиксная, то слова Pi,..., /3 n _i не являются префиксами /3. С другой стороны, /3 не являетсяпрефиксом слов /Зх,..., /З п -ь иначе было бы /3 = Pj, а значит, /3j было бы префиксом /Зп.
Тогда схема а ' \ = { а i —» / 3 i , . . . , а п —> /3) тоже префиксная, причёмчтоLA'{P) = U P ) противоречит оптимальности а.[ 2 ] Пусть теперь два кодовых слова /3 n -i и /Зп максимальной длины различаются пе в последнем разряде, то есть /3 n _i = Р'Ь', (Зп = Р"Ь", /3' ф /3", причёмР', Р" не являются префиксами для Pi,...,Рп-2 и наоборот. Тогда схема а': =: — (ai —> P i , . . . , а п - 2 —• /З п _ 2 , a n _ i —> /З'Ь', a n —> /3") также является префиксной,причём LA'{P) = 1<j{P) — РП, что противоречит оптимальности а.[ 3 ] Пусть кодовых слов максимальной длины больше двух. Тогда среди них найдутся два, которые отличаются не только в последнем разряде, что противоречитуже доказанному пункту 2.•Если crn-i = (A* —> A ) ™ ^ 1 — схема оптимального префиксного кодирования для распределения вероятностей Р = pi ^ ... ^ рп-\ > 0 и pj = q' + q",причёмТЕОРЕМАPj-1Р\>^ pj+i>Рп-1^ q' > q" > 0,то кодирование со схемойап=—• Pi,...,aj-ia n _ i —> Pn-i,aj—• Pj-i,dj+i—> Pj+i,• • •,—• PjO, an —• /3jl)является оптимальным префиксным кодированием для распределениястей Рп = pi,..
.,pj-i,pj+1,...,pn-i,q',q".ДОКАЗАТЕЛЬСТВОвероятно-Заметим следующее.[ 1 ] Если cr n -i было префиксным, то а п тоже будет префиксным по построению.[ 2 ] Цена кодирования для схемы а п больше цены кодирования для схемы a n - iна величину pj\1аЛРп)= Plh+P2h+ pn_1/n_1+ • • .+Pj-llj-l+pj+llj+l+ . . .++ q'{lj + 1) + q" (I j + 1) == pih + ... + Pn-iln-i+ lj{q' + Я") + (я' + Я") == pih + . •.
+pn_i/n_i+ljPj +Pj = U - i ( P n - i ) +Pj-2196.2. Кодирование с минимальной избыточностью[ 3 ] Пусть некоторая схема а'п : ={аг —>i оптимальна для Р п . Тогда полемме 2 два кода максимальной длины различаются в последнем разряде: а'п == (а\ —* (3[,..., ап-2 —• (3'п_2,ап-1 —> /30, ап —• (31).
Положим I': = \(3\ и рассмотгрим схему а'п_х: =(а\а^ —»•/?,...,а п _ 2 —•Де j определено так,чтобы pj-1 > g' 4- g" ^ Pj+i- Цена кодирования для схемы а'п больше ценыкодирования для схемы сг'п_1 также на величину pj\1*>п (Рп) = hpi + ... + ln-2Pn-2 + (I' + 1 )q' + {I' + 1 )q" == llPl + ... + ln-2Pn-2 + l'{q' + q") + (q' + q") =[ 4 ] Схема a'n — префиксная, зиачит, схема cr'n_l — тоже префиксная.[ 5 ] Схема crn_i — оптимальна, зиачит, la> {Pn-i) ^ррlp[6 ] Имеем: 1аЛ п) = 1<тп-А п-\) + Pj ^ a'n_1{ n-i)+Pjоптимальна, значит, схема а п также оптимальна.lan-i(Pn-i)=la'n{pn)-Но схемаа'п•6.2.5. Алгоритм ХаффменаРекурсивный алгоритм Хаффмена 1 строит схему оптимального префиксного алфавитного кодирования для заданного распределения вероятностей появлениябукв.Алгоритм 6.2 Построение оптимальной схемы — рекурсивная процедура HuffmanВход: п — количество букв, Р : array [l..n] of real — массив вероятностей букв,упорядоченный по убыванию.Выход: С : array [l..n, 1..L] of 0..1 — массив элементарных кодов, t : array [l..n]of 1..L — массив длин элементарных кодов схемы оптимального префиксногокодирования,if га = 2 thenС[ 1,1]: =0;^[1]: = 1 { первый элемент }С[2,1]: = 1; £[2]: = 1 { второй элемент }elseq: = Р[п - 1] + Р[п] { сумма двух последних вероятностей }j : = Up (га, q) { поиск места и вставка суммы }Huffman(P,га- 1) { рекурсивный вызов }Down (га, j ) { достраивание кодов }end ifФункция Up находит в массиве Р место, в котором должно находиться число q (см.
предыдущую теорему), и вставляет это число, сдвигая вниз остальныеэлементы.1Дэвид А. Хаффмен (1925-1999).220Глава 6. Кодирование 220Вход: п — длина обрабатываемой части массива Р, q — вставляемая сумма.Выход: измененный массив Р.j : = 1 { место вставляемого элемента }for i from п — 1 downto 2 doif P[i - 1] < q thenP[i) : = P[i — 1] { сдвиг элемента массива }elsej : = г { определение места вставляемого элемента }exit for г { всё сделано — цикл не нужно продолжать }end ifend forP[j] '• = 4 { запись вставляемого элемента }return jПроцедура Down строит оптимальный код для п букв на основе построенногооптимального кода для п — 1 буквы.
Для этого код буквы с номером j временноисключается из массива С путем сдвига вверх кодов букв с номерами, большимиj, а затем в конец обрабатываемой части массива С добавляется пара кодов,полученных из кода буквы с номером j удлинением на 0 и 1 соответственно.Здесь С [г, *] означает вырезку из массива, то есть г-ю строку массива С.Вход: п — длина обрабатываемой части массива Р, j — номер «разделяемой» буквы.Выход: оптимальные коды в первых п элементах массивов С ис: — C[j, *] { запоминание кода буквы j }I •' ={ и длины этого кода }for г from j to п - 2 doC[i, *]: = С [г + 1, *] { сдвиг кода }i[i] : = £[i + 1] {и его длины }end forС[п — 1, *]: = с; С[п, *]: = с { копирование кода буквы j }С[п - 1,1 + 1]: = 0; C[n, I + 1]: = 1 { наращивание кодов }1[п — 1]: = J + 1; i[n]: = I + 1 { и увеличение длин }ОБОСНОВАНИЕД Л Я пары букв при любом распределении вероятностей оптимальное кодирование очевидно: первой букве нужно назначить код 0, а второй — 1.Именно это и делается в первой части оператора if основной процедуры Huffman.Рекурсивная часть алгоритма в точности следует доказательству теоремы предыдущего подраздела.
С помощью функции Up в исходном упорядоченном массивеР отбрасываются две последние (наименьшие) вероятности, и их сумма вставляется в массив Р, так чтобы массив (на единицу меньшей длины) осталсяупорядоченным. Заметим, что при этом место вставки сохраняется в локальной переменной j. Так происходит до тех пор, пока не останется массив из двухэлементов, для которого оптимальный код известен. После этого в обратном порядке строятся оптимальные коды для трёх, четырёх и т. д. элементов. Заметим,что при этом массив вероятностей Р уже не нужен — нужна только последовательность номеров кодов, которые должны быть изъяты из массива кодов ипродублированы в конце с добавлением разряда.
А эта последовательность хранится в экземплярах локальной переменной j, соответствующих рекурсивнымвызовам процедуры Huffman.•2216.3. Помехоустойчивое кодированиеПример Построение оптимального кода Хаффмена для п = 7. В левой частитаблицы показано изменение массива Р, а в правой части — массива С. Позиция, соответствующая текущему значению переменной j, выделена полужирнымначертанием шрифта.0,200,200,230,370,400,6001000110100,200,200,200,230,370,40100011011110,230,190,190,200,200,120,180,190,200,110,120,180,090,110110110000001100000101000101001101100100,09ООНЦена кодирования составляетО, 20 х 2 + 0, 20 х 2 + 0,19 х 3 + 0,12 х 3 + 0,11 х 3 + 0,09 х 4 + 0,09 х 4 = 2, 78,что несколько лучше, чем в кодировании, полученном алгоритмом Фано.6.3. Помехоустойчивое кодированиеНадёжность электронных устройств по мере их совершенствования всё времявозрастает, по, тем не менее, в их работе возможны ошибки, как систематические, так и случайные.
Сигнал в канале связи может быть искажён помехой,поверхность магнитного носителя может быть повреждена, в разъёме может бытьпотерян контакт. Ошибки аппаратуры ведут к искажению или потере передаваемых или хранимых данных. При определённых условиях, некоторые из которыхрассматриваются в этом разделе, можно применять методы кодирования, позволяющие правильно декодировать исходное сообщение, несмотря па ошибкив данных кода. В качестве исследуемой модели достаточно рассмотреть каналсвязи с помехами, потому что к этому случаю легко сводятся остальные.
Например, запись на диск можно рассматривать как передачу данных в канал, а чтениес диска — как приём данных из капала.6.3.1. Кодирование с исправлением ошибокПусть имеется канал связи, содержащий источник помех. Помехи проявляютсяв том, что принятое сообщение может отличаться от переданного. Опишем этоотличие в функциональной форме:К-^К',К,К'еВ*,где К —множество переданных, а К' — соответствующее множество принятыхпо каналу сообщений, подразумевая, что разные вызовы «функции» С с одними тем же аргументом могут возвращать различные результаты. Кодирование F(вместе с декодированием F~l), обладающее тем свойством, что222Глава 6. Кодирование 222S - ^ K - ^ K ' ^ S , \ / s e S c A * (F~1(C(F(s)))= s),называется помехоустойчивым, или самокорректирующимся, или кодированиемс исправлением ошибок.
Без ограничения общности можно считать, что А = В == {0,1}. Кроме того, естественно предположить, что содержательное кодирование (вычисление F и F~l) выполняется на устройстве, свободном от помех, тоесть F и F'1 являются функциями в обычном смысле.ЗАМЕЧАНИЕФункция F - 1 является декодированием для кодирования F, но она не является обратнойфункцией для функции F в смысле определений подраздела 1.6.2.Если про источник помех С ничего не известно, то функции F и F - 1 не могутбыть определены, за исключением тривиальных случаев, когда S = 0 или \S\ = 1.Таким образом, для решения поставленной задачи необходимо иметь описаниевозможных ошибок (проявлений помех).Ошибки в канале могут быть следующих типов:• Он->1, 1 I—> 0 — ошибка типа замещения разряда;• О I—• е, 1 и е - ошибка типа выпадения разряда;*• е н> 1, s I—> 0 — ошибка типа вставки разряда.Канал характеризуется верхними оценками количества ошибок каждого типа,которые возможны при передаче через канал сообщения определённой длины п.Общая характеристика ошибок канала (то есть их количество и типы) обозначается 6 = (61,62,63), где£3 — верхние оценки количества ошибок каждоготипа соответственно.Пример Допустим, что имеется канал с характеристикой <5 = (1,0,0), то естьв канале возможно не более одной ошибки типа замещения разряда при передаче сообщения длины га.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
