277
правок
Изменения
м
→Однозначно декодируемый код
|author=Марков А.А.
|statement=Пусть <tex>\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</tex>. Тогда если кодирование <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 классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения).
{{Лемма
