?

Log in

No account? Create an account

Палимпсестные коды - Общество дровосеков Бердичева по изучению Мишны

Apr. 4th, 2015

08:22 pm - Палимпсестные коды

Previous Entry Share Next Entry

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

Tags:

Comments:

[User Picture]
From:maksa
Date:April 5th, 2015 06:47 am (UTC)
(Link)
Непонятно. Что если надо записать B на место B?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 5th, 2015 07:03 am (UTC)
(Link)
То всё отлично, ничего не надо изменять.
(Reply) (Parent) (Thread)
[User Picture]
From:maksa
Date:April 5th, 2015 08:03 am (UTC)
(Link)
Точно. Просто с телефона читал, всё сразу не уместилось на экране и в голове.
(Reply) (Parent) (Thread)
[User Picture]
From:oldjackaroo
Date:April 5th, 2015 04:41 pm (UTC)
(Link)
А я всегда недоумевал, как на RO диске меняют оглавление, когда туда что-то дописываешь...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:April 5th, 2015 04:49 pm (UTC)
(Link)
Оглавление там всегда в конце записанного участка, со ссылками назад.
(Reply) (Parent) (Thread)
[User Picture]
From:oldjackaroo
Date:April 5th, 2015 05:04 pm (UTC)
(Link)
Я примерно так и представлял, но RO диск можно рассматривать состоящим из тритов - битов с 3 состояниями, 0, 1, не-записан, где не-записан можно изменить на 0 или 1, а 0 или 1 - уже ни на что. Соответственно, можно использовать некоторую троичную модификацию палимпсестного кода.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 5th, 2015 05:07 pm (UTC)
(Link)
Увы, состояний поверхности бывает всего два: луч или отражается в приемник, или не отражается.
(Reply) (Parent) (Thread)
[User Picture]
From:oldjackaroo
Date:April 5th, 2015 05:12 pm (UTC)
(Link)
А я думал, они умеют распознавать незаписанную поверхность.

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

Но тогда тем более, твой код в чистом виде. Или там технически невозможно один бит выжечь, а не целый блок?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:April 5th, 2015 05:37 pm (UTC)
(Link)
Там бешеное количество уровней кодирования. На самом нижнем уровне - код "8 в 14", требование которого - наличие от минимум 2 до максимум 10 нулей между каждой парой единиц (ямок). Синхросигнал вырабатывается на основании импульсов, соответствующих единицам, как наибольший общий делитель интервалов между единицами. Незаписанная поверхность не дает синхросигнала. Ищут, конечно, двоичным поиском, на некоторых драйвах это даже было слышно.
Поверх этого идут корректирующие коды (разные для аудио и данных), так что на оптических носителях палимпсестным кодам ничего не светит. Возможно, на флеше это можно как-то использовать, чтобы вдвое снизить частоту необходимых стираний, и тем самым заметно ускорить запись.
(Reply) (Parent) (Thread)
[User Picture]
From:oldjackaroo
Date:April 5th, 2015 06:14 pm (UTC)
(Link)
Спасибо. Познавательно.
(Reply) (Parent) (Thread)