277
правок
Изменения
→Однозначно декодируемый код
<tex>b_{i_1} = b_{j_1}</tex>; <tex>b_{i_2} = b_{j_2}</tex>; ... <tex>b_{i_n} = b_{j_m}</tex>;
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
{{Определение
|neat = 1
|definition=Слово <tex>\bar{b} \in B^*</tex> называется неприводимым, если <tex>\bar{b}</tex> декодируется неоднозначно, однако, при выбрасывании из <tex>\bar{b}</tex> любого связного непустого куска получается слово, которое декодируется не более, чем одним способом.
}}
Где <tex>B</tex> — кодовый алфавит, а <tex>B^*</tex> — строчки (слова) из <tex>B</tex>.
{{Теорема
|id=идентификатор (необязательно), пример: th1. |author=Марков А.А.|statement=Для любого однозначно декодируемого кода выполняется [[Неравенство Крафта]]Пусть <reftex>Новиков Ф\phi : a_i \rightarrow B_i \ (i = 1,2,..А,r)</tex> - некоторое кодирование. <br>Пусть <tex>W</tex> — максимальное число кодовых слов, которые "Дискретная математика для программистовпомещаются"подряд внути кодового слова. Пусть <tex>l_i</tex> - длина слова <tex>B_i</tex> и <tex>L = \sum_{i=1}^r l_i</reftex>. Тогда если кодирование <tex>\phi</tex> не взаимно однозначно, то существуют два различных слова <tex>a' \in A^*</tex>, <tex>a'' \in A^*</tex>, <tex>|a'| \leqslant \left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor</tex>, <tex>|a''| \leqslant \left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor</tex> и <tex>\phi (a') = \phi (a'')</tex>|proof=Пусть <tex>\phi</tex> не является взаимно однозначным. Тогда существует некоторое слово <tex>\bar{b_1}</tex>, которое допускает две расшифровки. Если слово <tex>\bar{b_1}</tex> не является неприводимым, то выбрасывая из <tex>\bar{b_1}</tex> куски несколько раз, получим неприводимое слово <tex>\bar{b}</tex>; иначе, положим <tex>\bar{b} = \bar{b_1}</tex>. Очевидно, это всегда можно сделать. Рассмотрим любые две декодировки слова <tex>\bar{b}</tex>. Разрежем слово <tex>\bar{b}</tex> в концевых точках кодовых слов каждого из разбиений. Слова нового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементарными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения).{{Лемма|statement=Если <tex>\bar{b}</tex> — неприводимое слово, то все слова <tex>\beta_1, \beta_2,..,\beta_m</tex> II класса различны.|proof=Пусть <tex>\beta' = \beta''</tex>. Тогда, очевидно, слово <tex>\bar{b}</tex> не будет неприводимым, поскольку при выкидывании отрезка между <tex>\beta'</tex> и <tex>\beta''</tex>, вместе с любым из этих слов, получим снова две различные расшифровки этого слова.
}}
Таким образом, все <tex>\beta_1, \beta_2,..,\beta_m</tex> разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит <tex>(l_1 – 1) + (l_2 – 1) + ... + (l_r – 1) = L – r</tex>. Слова из второго класса разбивают слово не более чем на <tex>L – r + 1</tex> кусков. Рассмотрим пары соседних кусков. Тогда согласно одному разбиению в одной половинке уложится не более одного кодового слова, а в другой — не более <tex>W</tex> (согласно второму разбиению ситуация симметрична). Всего пар кусков не больше, чем <tex>\left \lceil \frac{L-r+1}{2} \right \rceil \leqslant \frac{Теорема|statement=Зная кодовые словаL-r+1}{2}</tex>, мы может определить можно ли составить а в каждом из них однозначно декодируемый кодукладывается слов не более чем <tex>W + 1<ref/tex>Яблонский С.В "Введение Отсюда число кодовых слов в дискретную математику".любом разбиении не превосходит <tex>\frac{L-r+1}{2}</tex><tex>(W+1)</tex>, а поскольку число целое, то не превосходит и целой части <tex>\left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor</reftex>. Теорема доказана.
}}
