Изменения

Перейти к: навигация, поиск

Кодирование информации

18 байт убрано, 19:14, 4 сентября 2022
м
rollbackEdits.php mass rollback
=== Пример кодирования ===
<tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>;  <tex> Z = \mathcal {f} 0, 1 \mathcal {g}</tex> <tex>c(a) = 00; </tex> <tex> c(b) = 01; </tex> <tex> c(c) = 1;</tex> Закодируем строку: <tex>abacaba</tex>:  <tex>c^*(abacaba) = 0001001000100</tex> 
Такой код можно однозначно разбить на слова:
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</tex>
=== Преимущества префиксных кодов ===
=== Пример неудачного декодирования ===
Предположим, что последовательность <tex>abacaba</tex> из примера передалась неверно и стала:
<tex>c^{**}(abacaba) = 0001001\ 1\ 00100</tex> 
Разобьем ее согласно словарю:
<tex> 00\ 01\ 00\ 1\ 1\ 00\ 1\ 00</tex> <tex>a\quad b\quad a\ c\ c\quad a\ c\ a</tex> 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
=== Не префиксный однозначно декодируемый код ===
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
<tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>;  <tex>Z = \mathcal {f} 1, 2, 3 \mathcal {g}</tex>; <tex>c(a) = 1; </tex> <tex> c(b) = 12; </tex> <tex> c(c) = 31;</tex> Закодируем <tex>abbca</tex>, получим кодовую строку : <tex>11212311</tex> 
Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица.
После декодирования получаем: <tex>abbca</tex>
== См. также ==
== Источники информации ==
* [http://en.wikipedia.org/wiki/Prefix_code Wikipedia {{---}} Prefix_codePrefix code]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
* Джеймс Андерсон. «Дискретная математика и комбинаторика» {{---}} «Вильямс», 2004 г. {{---}} 960 стр. {{---}} ISBN 978-0-13-086998-2
1632
правки

Навигация