Палимпсестные коды
Если есть двоичный носитель информации, биты которого можно изменять только в одну сторону (например, из 0 в 1), то можно ли придумать код, позволяющий писать на этом носителе произвольные данные не однажды, а большее количество раз, чтобы суммарный объем этих данных превосходил объем носителя?
Для алфавита из четырех символов - A, B, C, D - выберем следующие трехбитные коды для первой записи:
000 - A
001 - B
010 - C
100 - D
Если в той позиции, куда мы хотим записать что-то повторно, был символ A, то нет проблем.
Если же мы хотим сделать B из C или D, то логично будет назначить для "вторичного B" код 110. Аналогично с "вторичными" C и D. Тогда для вторичного A остается код 111, итого
000 - A
001 - B
010 - C
011 - D
100 - D
101 - C
110 - B
111 - A
Таким образом мы тратим 3 бита, позволяя записывать 2 бита дважды - уже экономия.
Патент 1982 года показывает, что можно повторно записать 26 символов в 7 битах. До сих пор неизвестно, существует ли 7-битный код для 27 символов.
Для алфавита из четырех символов - A, B, C, D - выберем следующие трехбитные коды для первой записи:
000 - A
001 - B
010 - C
100 - D
Если в той позиции, куда мы хотим записать что-то повторно, был символ A, то нет проблем.
Если же мы хотим сделать B из C или D, то логично будет назначить для "вторичного B" код 110. Аналогично с "вторичными" C и D. Тогда для вторичного A остается код 111, итого
000 - A
001 - B
010 - C
011 - D
100 - D
101 - C
110 - B
111 - A
Таким образом мы тратим 3 бита, позволяя записывать 2 бита дважды - уже экономия.
Патент 1982 года показывает, что можно повторно записать 26 символов в 7 битах. До сих пор неизвестно, существует ли 7-битный код для 27 символов.