Критерий однозначности декодирования

Рассмотрим алфавитное кодирование для алфавитов U и D, задаваемое схемой :

a₁ – B₁,

… ( )

a_r – B_r.

Полагаем S¹(U)=S(U), т.е. источник сообщений порождает множество всех слов в алфавите U. Очевидно, что алфавитное кодирование порождает отображение множества S(U) в множество S(D). Обозначим через S_(D) образ множества S(U) в этом отображении.

В случае, когда отображение S(U) на S_(D) взаимно однозначно, возможно декодирование, т.е. возможно по коду В однозначно восстановить исходное сообщение A, кодом которого является B.

Пример . Рассмотрим алфавитное кодирование, для которого U={a₁,a₂}, D={b₁,b₂} и схема имеет вид:

: a₁ – b₁,

a₂ – b₁ b₂.

Пусть нам известен код B, нам нужно восстановить сообщение A. Произведем разбиение слова B на элементарные коды B=b₁b₁ b₂ b₁ b₁ b₁ b₂ b₁ b₂  A=a₁ a₂ a₁ a₁ a₂ a₂ .

Данное алфавитное кодирование свойством взаимной однозначности обладает.

Определение : Пусть слово В имеет вид: В= В¹В¹¹. Тогда слово В¹ называют началом или префиксом слова B, а В¹¹ - концом или суффиксом слова В.

Определение : Схема  обладает свойством префикса, если для любых i и j (1 i, j r, i j ) слово В_i не является префиксом слова B_j.

Теорема 1. Если схема  обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.

Доказательство: Предположим, что некоторое слово В из S_(D) допускает две расшифровки, а значит и два разбиения на элементарные коды:

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

Теорема доказана .

Пусть . Из предыдущего примера :

: a₁ – b₁,

a₂ – b₂b₁,

Схемы и одновременно обладают свойством взаимной однозначности.

Теорема 2 . Если либо схема , либо схема обладает свойством префикса, тогда алфавитное кодирование, задаваемое ( ), будет взаимно однозначным.

Пример .

U={a₁,a₂,a₃} D={b₁,b₂,b₃}

: a₁ - b₁ : a₁ - b₁

a₂ - b₁ b₂ a₂ - b₂ b₁

a₃ - b₃ b₁ a₃ - b₁ b₃

Заметим, что схемы и не обладают свойством префикса, но алфавитное кодирование свойством взаимной однозначности обладает.

Введем ряд обозначений:

l(B) – длина слова B ,

l(B_i) = l_i (i = 1,2, … , r),

L = l(B₁…B_r) – вся длина кодов схемы .

Пусть B_i = ^ … ^ 

 нетривиальное разложение элементарного кода B_i, т.е. разложение, отличное от разложения B_i = B_i ( ^=^= .

В этом разложении предполагается, что :

1. ^ не может оканчиваться элементарным кодом .

2. ^не содержит в качестве префикса элементарного кода .

3. Параметр  может быть целым числом 0 .

Соотношение (1) означает, что в элементарном коде B_i можно отбросить некое начало ^ и некий конец ^ так, что оставшаяся часть разбивается на элементарные коды.

Очевидно, что для каждого B_i число разложений (1) конечно. Обозначим через W максимум чисел , взятых по всем разложениям B_i и по всем i, т.е. W=max  .

Пример: U={a₁,a₂,a₃,a₄,a₅} ,

D={b₁,b₂,b₃} .

 a₁ - b₁ b₂ = B₁ l₁=2 L = 16

a₂ - b₁ b₃ b₂=B₂b₂ l₂=3 W = 2

a₃ - b₂ b₃ = B₃ l₃=2

a₄ - b₁ b₂ b₁ b₃= B₁B₂ l₄=4

a₅ - b₂ b₁ b₂ b₂ b₃= b₂B₁B₃ l₅=5

Теорема 3 (А.А. Марков) . Для всякого алфавитного кодирования со схемой существует такое N₀ , что проблема взаимной однозначности алфавитного кодирования сводится к проблеме для кодирования конечного множества - всевозможных слов в алфавите U, длина которых

N₀ и N₀ .

Доказательство. Если в алфавитном кодировании нарушена взаимная однозначность, то найдется такое слово B, которое допускает по крайней мере 2 различные расшифровки A¹ и A¹¹. Для доказательства теоремы достаточно установить, что можно найти такое слово B, что для его расшифровок A¹ и A¹¹ имеют место неравенства :

l(A¹), l(A¹¹) .

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

С самого начала можно предполагать, что слово B – неприводимо. Рассмотрим A¹ и A¹¹ (его 2 расшифровки). С ними связаны 2 разбиения слова B на элементарные коды – верхнее Т₁ и нижнее Т₂ :

Пусть Т получается путем одновременного разбиения Т₁ и Т₂.

Слова этого нового разбиения Т разделим на 2 класса:

1. слова, являющиеся элементарными кодами (входят каждое ровно в одно разбиение),

2. все остальные слова (изображены жирными отрезками).

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

Покажем, что каждые 2 слова ¹и ^ из второго класса различны

(^^. Предположим , что ^^  B B¹¹B¹¹¹¹B¹¹¹=B¹B¹¹B^{111 .}

Утверждается, что слово B¹¹B¹¹¹, получающееся из B путем выбрасывания куска B¹¹¹¹, допускает по крайней мере две расшифровки. Для расположения слов ¹и ^ возможны 4 случая :

В случае а) при выбрасывании куска B¹¹¹¹ и сдвигании кусков B¹¹ и B¹¹¹ верхнее (нижнее) разбиение получается из склейки частей верхнего (нижнего) разбиения.

В случае б) верхнее (нижнее) разбиение получается из cклейки части верхнего (нижнего) разбиения для куска B¹¹ и нижнего (верхнего) разбиения для B¹¹¹ .

Нетрудно видеть, что случай в) сводится к случаю а), случай г) – к случаю б). Для этого в в) и г) нужно поменять ролями разбиения Т₁ и Т₂.

Итак, для слова B¹¹ B¹¹¹ во всех случаях получаем по крайней мере 2 расшифровки . Таким образом получили противоречие.

Число р слов второго класса не превосходит числа непустых собственных начал элементарных кодов, т.е.:

p (l(B₁) - 1) + (l(B₂) - 1) +…+ (l(B_r) - 1) = L – r .

Слова из второго класса разбивают слово В не более чем на L – r + 1 кусков, некоторые из них могут быть пустыми (см. рис. ниже) .

Пусть  ⁰ =  ^p+1 = . Рассмотрим один из кусков, расположенный между словами  ^j и  ^j+1 (j=0,…, p):

 ^jB_i1…B_i ^j+1 .

В этом куске все слова B_i1,…, B_i принадлежат одному и тому же разбиению слова B, например Т₁, а слово

 ^jB_i1…B_i ^j+1 = B_i

¹ ¹¹  ^p

B

принадлежит другому разбиению – Т₂ . При этом  W. Поэтому с каждым куском связаны  элементарных кодов одного разбиения и один элементарный код другого разбиения.

Если взять теперь два соседних куска:

входят в одно разбиение , а

входят в другое разбиение .

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

.

Мы получаем, что .

Пусть N₀ = max(l(A¹),l(A¹¹)), то взаимная однозначность кодирования уже нарушается на множестве , т.к. .

Теорема полностью доказана.

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

Пример . (См. предыдущий пример). Мы имеем r=5, W=2, L=16, и получаем =5¹⁹, что весьма велико.

Алгоритм распознавания однозначности декодирования

Из доказательства критерия однозначности декодирования можно извлечь достаточно эффективный алгоритм для распознавания возможности

декодирования. Этот алгоритм формулируется на языке теории графов.

Пусть алфавитное кодирование задано схемой  : а₁ - B₁,

… ()

а _r - B _r .

Для любого элементарного кода B_i рассмотрим все нетривиальные представления вида B_i = ^ … ^. 2)

Пусть D₀ – множество, содержащее:

а) пустое слово  ;

б) слова , которые встречаются в (2) как в форме префиксов, так и окончаний.

Далее, каждому слову из D₀ сопоставим точку на плоскости :

¹



^p ¹¹

^. . . .

Точки на плоскости, рассматривая как вершины графа, соединим ребрами в соответствии разложениям вида (2). Полученный ориентированный граф обозначим через Г().

Определение. Слово В , допускающее не менее двух расшифровок, называется неприводимым, если каждое слово В¹ , получающееся из В путем выбрасывания непустого куска, допускает не более одной расшифровки.

Теорема 4. Алфавитное кодирование со схемой  не обладает свойством взаимной однозначности  Г() содержит ориентированный цикл, проходящий через вершину .

Доказательство. Необходимость: Пусть алфавитное кодирование не обладает свойством взаимной однозначности. Тогда найдется неприводимое слово B вида

,

для которого

,

,

….

.

Поэтому в графе Г() имеется ориентированный цикл, проходящий через вершину .

Достаточность : Пусть Г() содержит ориентированный цикл, проходящий через вершину . Тогда слово В, где

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

.

Теорема доказана.

Замечание. Алгоритм распознавания однозначности декодирования алфавитного кодирования со схемой  состоит из построения графа Г() и выявления в нем ориентированных циклов, проходящих через .

Пример . Рассмотрим алфавитное кодирование со схемой :

a₁ - b₁ b₂

a₂ - b₁b₃ b₂

a₃ - b₂ b₃ ()

a₄ - b₁ b₂ b₁ b₃

a₅ - b₂ b₁ b₂ b₂ b₃

Имеем следующие нетривиальные разложения :

В₁=(b₁)(b₂), В₂=(b₁)( b₃b₂)= ( b₁b₃) (b₂), В₃=(b₂)(b₃),

В₄=(b₁)(b₂b₁b₃)= ( b₁b₂) (b₁b₃)= (b₁b₂b₁) (b₃),

В₅=(b₂)( b₁b₂b₂b₃)= (b₂)( b₁b₂) (b₂b₃)= (b₂b₁) (b₂b₂b₃)= (b₂b₁b₂) (b₂b₃)= (b₂b₁b₂) (b₂b₃)= (b₂b₁b₂b₂) (b₃).

Очевидно, D₀ ={b₂ , b₁b₃} и с ним связаны разложения

В₂ =( b₁ b₃)( b₂) ,

В₄ =( b₁ b₂)( b₁ b₃) = В₁(b₁ b₃),

В₅ =( b₂)( b₁ b₂)( b₂ b₃)= (b₂) В₁ В₃.

Это дает возможность построить граф Г() . Г() содержит ориентированный цикл, порождающий слово В, где

В = В₁ b₁ b₃ b₂ В₁ В₃.



В₁ В₃ В₁

b₂  b₁b₃

Слово В имеет две расшифровки :

В = (В₁ b₁ b₃ )( b₂ В₁В₃ ), т.е. А¹=а₄ а₅ ,

В = В₁ (b₁ b₃ b₂ )В₁ В₃ , т.е_. А¹¹= а₁ а₂ а₁ а₃ .

Пример. Рассмотрим алфавитное кодирование со схемой :

a₁ - b₁ ,

a₂ - b₂b₁ ,

a₃ - b₁b₂b₂ , ()

a₄ - b₂b₁b₂b₂ ,

a₅ - b₂b₂b₂b_{2 .}

Имеем сдедующие нетривиальные разложения :

В₂=(b₂) b₁= (b₂)В₁

В₃=(b₁)(b₂b₂)= В₁(b₂b₂), В₃=(b₁b₂)(b₂);

В₄=(b₂)(b₁)(b₂b₂)= (b₂)В₁(b₂b₂);

В₄=(b₂)(b₁b₂b₂)=(b₂)В₃;

В₄=(b₂b₁)(b₂b₂)=В₂(b₂b₂); В₄=(b₂b₁b₂)(b₂) ;

В₅=(b₂)(b₂b₂b₂)= (b₂b₂)(b₂b₂) =(b₂b₂b₂)(b₂) .

Очевидно, D₀= {b₂ , b₂b₂, b₂b₂ b₂ } и с ним связаны разложения

В₁=b₁ ,

В₂=b₂B₁ ,

В₃= В₁ (b₂b₂),

В₄=(b₂)В₁(b₂b₂); В₄=(b₂)В₃; В₄= В₂(b₂b₂);

В₅=(b₂)(b₂b₂b₂)= (b₂b₂)(b₂b₂) =(b₂b₂b₂)(b₂).

Мы получаем граф Г(), не содержащий ориентированного цикла, проходящего через вершину  :

Следовательно, алфавитное кодирование со схемой  обладает свойством взаимной однозначности. Заметим, данное заключение не может быть выведено из теоремы 2.

Замечание. Из теоремы 4 следуеталгоритм распознавания однозначности декодирования.

Пусть С() – алфавитный код. Пусть S₁ - множество слов , обладающих следующим свойством : слово  является собственным суффиксом некоторого кодового слова В и собственным префиксом некоторого кодового слова В₁ , отличного от В , и, кроме того, не является кодовым словом кода С(). Положим S= S₁{}. Сопоставим коду С() ориентированный граф Г¹(), вершинами которого являются элементы множества S, и в котором дуга, ведущая из вершины  в вершину  (), присутствует тогда и только тогда, когда найдется кодовое слово В и последовательность Р= кодовых слов такие, что . При этом последовательность Р может быть и пустой, если ни одна из вершин ,  не совпадает с . Дуге, ведущей из  в , припишем последовательность Р. Дуги вида (,), ведущие из  в  , рассматриваться не будут, за исключением случая =. Дуга (петля) из  в  присутствует в графе Г¹() тогда и только тогда , когда существует слово В и последовательность кодовых слов Р= , где S 2, такие, что В= . Петле (,) припишем слово В.

Пример: С()={a, ab, cab, baac} , S ={, b, c}.

B = a b a a c a b b

a

B = a b a a c a b  aa

ab c

В данном примере кодирование не является взаимно однозначным.

Самокорректирующиеся коды. Коды Хэмминга

Равномерное кодирование. Пусть {A₁, …, A_s} - некоторое подмножество попарно различных слов в алфавите U, имеющих одинаковую длину m . Очевидно, что каждое слово А, которое допускает разложение вида , имеет единственное разложение. S¹(U)- некоторое подмножество слов в U, допускающее разложение вида А. Рассмотрим схему A₁ - В₁ ,

… ()

A_s – В_s .

Схема  определяет равномерное кодирование : каждому слову ставится в соответствие слово , называемое кодом слова А.

Рассмотрим один частный случай равномерного кодирования.

Пусть U={0,1}, {A₁, … , A_s} – множество всех слов вида А=₁…_m в алфавите U, имеющих фиксированную длину m (здесь s = 2^m). Предположим, что в канале связи действует источник помех, который в словах из {A₁, …, A_s}, имеющих длину m, может выдавать ошибки не более чем в р символах. Совершенно ясно, что если передавать исходное сообщение ₁…_m (без предварительного кодирования), то на выходе канала невозможно будет установить, какое сообщение фактически было передано. В связи с этим возникает вопрос, нельзя ли осуществить кодирование слов А из множества {A₁, …, A_s}, т.е. слов вида ₁…_m , словами вида ₁ … _l длины l так, чтобы по коду ¹₁ … ¹_l , полученному на выходе канала при передаче кода ₁ … _l , можно было однозначно восстановить этот код, и, значит, исходное сообщение ₁…_m ? Коды, обладающие данным свойством, будем называть самокорректирующимися кодами относительно рассматриваемого источника помех.

Тривиальное решение задачи. U={0,1}; р=1, т.е. 0 1, 1 0. Искомый самокорректирующий код получается путем утроения символов исходного кода ₁₂…_m - ₁₁₁₂₂₂ … _m_m_m .

Тривиальное решение не является корректным, т.к. l = 3m, мы приходим к кодам, для которых данный источник помех может вызвать большее число ошибок, чем р.

Корректное построение самокорректирующихся кодов было осуществлено Хэммингом (1950 г.), им подробно был разобран случай р=1.

Сообщения ₁ … _m кодируются наборами ₁ … _l , где l – длина кода и l=m+k. При наличии источника помех возможны следующие варианты получения кодов на выходе :

на входе на выходе

₁₂ … _l

 ₁₂ … _l

…

На выходе число вариантов = l+1 . Для того, чтобы дополнительные k разрядов в коде ₁… _l хватало для кодировки перечисленных (l+1) случаев, или (l+1) слов, необходимо, чтобы 2^k l+1 или . (*)

Исходя из этих соображений выберем l как наименьшее целое число, удовлетворяющее неравенству (*) .

Дальнейшие построения будут состоять из трех этапов.

I. Построение кодов Хэмминга (описание алгоритма кодирования). Отрезок (1,2,…,l) разобьем на k последовательностей так : пусть V - произвольное натуральное число, 1 V l, и V_k … V₁ – его двоичная запись.

Последовательность 1, 3, 5, 7, 9, … содержит все числа V с V₁=1.

Последовательность 2, 3, 6, 7, 10, … содержит все числа V с V₂=1.

Последовательность 4, 5, 6, 7, 12, … содержит все числа V с V₃=1.

… . . . . . .

Последовательность 2^k-1, 2^k-1+1, … содержит все числа V с V_k=1.

Первыми членами этих последовательностей являются числа 1=2⁰ , 2=2¹, …, 2^k-1 , где 2^k-1 l, a 2^k l+1.

Члены _i набора ₁…_l, у которых индекс i{1,2,…,2^k-1}, называются контрольными членами, остальные – информационными. Легко видеть, что контрольных членов k, а информационных - l-k = m.

Правило построения набора ₁…_l по набору ₁…_m . Сначала определяются информационные члены ₃ = ₁,

₅ = ₂ ,

₆ = ₃,

. . .

Набор из информационных членов совпадает с набором ₁ … _m.

Далее определим контрольные члены : ₁ = ₃+₅+₇ +… (mod 2),

₂ = ₃+₆+₇ +… (mod 2),

₄ = ₅+₆+₇ +… (mod 2),

…

H_l¹ – множество всех построенных наборов ₁… _l .

II.Обнаружение ошибок в кодах Хэмминга. ₁… _l )H_l¹. Пусть при передаче кода ₁… _l произошла ошибка в S-м члене . Тогда на выходе канала было принято слово , где . Пусть S = S_k…S₁ - запись числа S в двоичном счислении. Покажем, как можно по коду найти число S. Рассмотрим число , где :

(1-я последовательность),

(2-я последовательность),

(3-я последовательность),

. . . . . . . . .

Покажем, что S=S¹.

Если S₁=0 , то S не принадлежит первой последовательности и тогда , поэтому S₁¹= 0.

Если S₁=1, то S принадлежит первой последовательности и тогда

, поэтому S₁¹=1.

Таким образом S₁ = S₁¹. Аналогично доказывается, что S₂ = S₂¹, ... , S_k = S_k¹. Значит S = S¹.

Если при передаче ошибки не произошло, то S¹ = 0. Если была ошибка, то член ¹_s заменяем на .

III. Декодирование. Этот шаг состоит в построении исходного сообщения ₁ … _m по коду ₁ … _l . Для этого , очевидно , достаточно взять информационные члены из кода ₁ … _l .

Пример. Построить самокорректирующийся код для m = 4. Находим наименьшее число l по неравенству (*) : , l=7, l=m+k, k=3. В соответствии с этапом 1 получаем самокорректирующийся код. Результат этого построения представлен в следующей таблице, в которой контрольные члены помечены звездочкой :

1*	2*	3	4*	5	6	7
0	0	0	0	0	0	0
1	1	0	1	0	0	1
0	1	0	1	0	1	0
1	0	0	0	0	1	1
1	0	0	1	1	0	0
0	1	0	0	1	0	1
1	1	0	0	1	1	0
0	0	0	1	1	1	1
1	1	1	0	0	0	0
0	0	1	1	0	0	1
1	0	1	1	0	1	0
0	1	1	0	0	1	1
0	1	1	1	1	0	0
1	0	1	0	1	0	1
0	0	1	0	1	1	0
1	1	1	1	1	1	1

В этой таблице сначала в столбцы с номерами 3, 5, 6 и 7 (информационные члены) вписываются сверху вниз наборы 0000, … , 1111. Затем по формулам

₁ = ₃+₅+₇ (mod 2),

₂ = ₃+₆+₇ (mod 2),

₄ = ₅+₆+₇ (mod 2)

заполняются столбцы с номерами 1, 2 и 4.

Пусть на вход канала поступил код 0110011, а в нем источник помех исказил 5-й член (S=5) . Тогда на выходе мы получим 0110111. Вычислим номер члена, в котором произошла ошибка. Мы имеем

S₁¹ = 0+1+1+1=1,

S₂¹ = 1+1+1+1=0,

S₃¹ = 0+1+1+1=1.

Следовательно, S¹ =101, т.е. S¹ == 5. Мы обнаружили член, в котором произошла ошибка, и S¹ =S.