Почему этот код уникально декодируется?

21

Исходный алфавит: {a,b,c,d,e,f}

Кодовый алфавит: {0,1}

  • a:0101
  • b:1001
  • c:10
  • d:000
  • e:11
  • f:100

Я думал, что для того, чтобы код был уникально декодируемым, он должен быть без префиксов. Но в этом коде кодовое слово c является префиксом кодового слова f , поэтому оно не является свободным от префикса. Однако мой учебник говорит мне, что его реверс не содержит префиксов (я этого не понимаю), и поэтому он уникально декодируется. Может кто-нибудь объяснить, что это значит, или почему это однозначно расшифровывается? Я знаю, что это удовлетворяет неравенству Крафта, но это только необходимое условие, а не достаточное условие.

2000mroliver
источник
10
Без префиксов подразумевается однозначное декодирование, но это не утверждение «тогда и только тогда». Смотрите, например, здесь .
dkaeae
Хорошо, я вижу, но в моем учебнике написано так: код A однозначно декодируется, поскольку его обратный код не содержит префиксов и поэтому уникально декодируется. Вы понимаете, что они подразумевают под его обратным кодом?
2000mroliver
1
Вероятно, просто код, полученный путем обращения всех кодовых слов.
dkaeae
и почему это подразумевает однозначное декодирование, я не понимаю
2000mroliver
1
cможет быть префиксом bи f, но оставшиеся суффиксы не существуют в коде. Когда вы переворачиваете код, суффиксы становятся префиксами, а затем он становится свободным от префиксов.
Бармар

Ответы:

26

Ваш код обладает свойством, что если вы перевернете все кодовые слова, то получите код префикса. Это подразумевает, что ваш код уникально декодируется.

Действительно, рассмотрим любой код C=x1,,xn , обратная сторона которого CR:=x1R,,xnR однозначно декодируется. Я утверждаю, что C также однозначно декодируется. Это потому, что

w=xi1xim if and only if wR=ximRxi1R.
На словах разложение w в кодовые слова C находятся во взаимно однозначное соответствие с разбиениями wR в кодовые слова из CR . Поскольку последние уникальны, так же как и первые.

Поскольку префиксные коды однозначно декодируются, из этого следует, что обратная сторона префиксного кода также однозначно декодируется. Это случай в вашем примере.

C

i=1n2|xi|1.

0,01,110.
111001001010

prefix00010011001110codeword001001
1

Юваль Фильмус
источник
2
Похоже, что в примере OP мы не можем декодировать первое кодовое слово после фиксированного количества цифр, существует бесконечно много случаев: 1001010101010101…может быть либо, fcccccc…либо caaa…, и нам, возможно, придется подождать до конца ввода, чтобы принять решение.
Берги
1
1,10,00
4
@Bergi Он всегда декодируется для любого конечного количества цифр. Всегда есть только один способ декодировать кодировку без остатка. Любая другая попытка закончится с запасными 1 или 0. Это потому, что код уникально декодируется, если мы сначала прочитаем его. Теоретически, если что-то однозначно декодируется в одном направлении, нет никакого смысла в том, что в другом направлении может быть более одного решения
slebetman
@slebetman Я имел в виду конечный префикс (с возможными остатками). Да, если мы берем весь ввод, он всегда декодируемый.
Берги
5

Если я дам вам какое-либо сообщение, которое вы должны декодировать, вы можете сделать следующее: Обратное сообщение, начиная с последнего бита, а не с первого бита. Переверните кодовые слова. Расшифруйте сообщение. Переверните декодированную строку.

Вы можете сделать это, потому что после обращения шести кодовых слов вы получите код без префикса: 1010, 1001, 01, 000, 11, 001 без префикса.

gnasher729
источник
0

Если без префикса означает то, что я думаю, обратный знак «а» начинается с 1, или 10, или 101, ни один из которых не является каким-либо другим действительным кодом.

Следовательно, если сообщение заканчивается 0101, оно может быть только «a», и вы можете применить аналогичную логику к предыдущему (ым) биту (ам).

Однако что, если нет конца, чтобы начать с? Ну, если первый бит равен 1, вы знаете, что это не «а» или «d». Второй бит исключит 'e' или {'b', 'c', 'f'}. Третий бит может привести к одному выбору, но если нет, то он четвертый бит уникален.

Как только вы доберетесь до уникальной последовательности, вы перезапустите алгоритм на следующем бите.

WGroleau
источник