Исходный алфавит:
Кодовый алфавит:
Я думал, что для того, чтобы код был уникально декодируемым, он должен быть без префиксов. Но в этом коде кодовое слово является префиксом кодового слова , поэтому оно не является свободным от префикса. Однако мой учебник говорит мне, что его реверс не содержит префиксов (я этого не понимаю), и поэтому он уникально декодируется. Может кто-нибудь объяснить, что это значит, или почему это однозначно расшифровывается? Я знаю, что это удовлетворяет неравенству Крафта, но это только необходимое условие, а не достаточное условие.
encoding-scheme
2000mroliver
источник
источник
c
может быть префиксомb
иf
, но оставшиеся суффиксы не существуют в коде. Когда вы переворачиваете код, суффиксы становятся префиксами, а затем он становится свободным от префиксов.Ответы:
Ваш код обладает свойством, что если вы перевернете все кодовые слова, то получите код префикса. Это подразумевает, что ваш код уникально декодируется.
Действительно, рассмотрим любой кодC=x1,…,xn , обратная сторона которого CR:=xR1,…,xRn однозначно декодируется. Я утверждаю, что C также однозначно декодируется. Это потому, что
w=xi1…xim if and only if wR=xRim…xRi1.
На словах разложение w в кодовые слова C находятся во взаимно однозначное соответствие с разбиениями wR в кодовые слова из CR . Поскольку последние уникальны, так же как и первые.
Поскольку префиксные коды однозначно декодируются, из этого следует, что обратная сторона префиксного кода также однозначно декодируется. Это случай в вашем примере.
источник
1001010101010101…
может быть либо,fcccccc…
либоcaaa…
, и нам, возможно, придется подождать до конца ввода, чтобы принять решение.Если я дам вам какое-либо сообщение, которое вы должны декодировать, вы можете сделать следующее: Обратное сообщение, начиная с последнего бита, а не с первого бита. Переверните кодовые слова. Расшифруйте сообщение. Переверните декодированную строку.
Вы можете сделать это, потому что после обращения шести кодовых слов вы получите код без префикса: 1010, 1001, 01, 000, 11, 001 без префикса.
источник
Если без префикса означает то, что я думаю, обратный знак «а» начинается с 1, или 10, или 101, ни один из которых не является каким-либо другим действительным кодом.
Следовательно, если сообщение заканчивается 0101, оно может быть только «a», и вы можете применить аналогичную логику к предыдущему (ым) биту (ам).
Однако что, если нет конца, чтобы начать с? Ну, если первый бит равен 1, вы знаете, что это не «а» или «d». Второй бит исключит 'e' или {'b', 'c', 'f'}. Третий бит может привести к одному выбору, но если нет, то он четвертый бит уникален.
Как только вы доберетесь до уникальной последовательности, вы перезапустите алгоритм на следующем бите.
источник