Палимпсестные коды

[spamsink]

Если есть двоичный носитель информации, биты которого можно изменять только в одну сторону (например, из 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 символов.

Comments

[maksa.livejournal.com]

Непонятно. Что если надо записать B на место B?

[spamsink]

То всё отлично, ничего не надо изменять.

[maksa.livejournal.com]

Точно. Просто с телефона читал, всё сразу не уместилось на экране и в голове.

[oldjackaroo.livejournal.com]

А я всегда недоумевал, как на RO диске меняют оглавление, когда туда что-то дописываешь...

[spamsink]

Оглавление там всегда в конце записанного участка, со ссылками назад.

[oldjackaroo.livejournal.com]

Я примерно так и представлял, но RO диск можно рассматривать состоящим из тритов - битов с 3 состояниями, 0, 1, не-записан, где не-записан можно изменить на 0 или 1, а 0 или 1 - уже ни на что. Соответственно, можно использовать некоторую троичную модификацию палимпсестного кода.

[spamsink]

Увы, состояний поверхности бывает всего два: луч или отражается в приемник, или не отражается.

[oldjackaroo.livejournal.com]

А я думал, они умеют распознавать незаписанную поверхность.

А как тогда они находят конец записанного участка? Сканируют всю поверхность? (Ну, или часть, предназначенную для оглавления? Или двоичный поиск?)

Но тогда тем более, твой код в чистом виде. Или там технически невозможно один бит выжечь, а не целый блок?

[spamsink]

Там бешеное количество уровней кодирования. На самом нижнем уровне - код "8 в 14", требование которого - наличие от минимум 2 до максимум 10 нулей между каждой парой единиц (ямок). Синхросигнал вырабатывается на основании импульсов, соответствующих единицам, как наибольший общий делитель интервалов между единицами. Незаписанная поверхность не дает синхросигнала. Ищут, конечно, двоичным поиском, на некоторых драйвах это даже было слышно.
Поверх этого идут корректирующие коды (разные для аудио и данных), так что на оптических носителях палимпсестным кодам ничего не светит. Возможно, на флеше это можно как-то использовать, чтобы вдвое снизить частоту необходимых стираний, и тем самым заметно ускорить запись.

[oldjackaroo.livejournal.com]

Спасибо. Познавательно.