?

Log in

No account? Create an account

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

Jan. 14th, 2017

08:59 am - По следам наших палимпсестных выступлений

Previous Entry Share Next Entry

Чуть менее 2 лет назад я писал о нерешенной проблеме палимпсестных кодов. Оказывается, эта задача была решена в прошлом году.

Короче, если вам нужно писать на перфоленте только большие латинские буквы плюс еще два символа, у вас есть только 7-дорожечная перфолента, но ее нужно экономить, то у вас есть шанс использовать уже однажды продырявленную перфоленту повторно для записи произвольного текста еще раз, если символы (A-Z, 1, 2) кодируются, например, так:

   0123456789ABCDEF
  +----------------
0 |1WHTRLZREOPVQATM
1 |GBFIDOANJRAX2KYC
2 |IVCAUILY2URLDBXF
3 |AJTMR1EPIQNZWGVS
4 |KMKBYSGDXIQ2RPIW
5 |NARGIVJQSFB1ZELU
6 |SRIOCZQKVCGEAN1J
7 |CLUWFXB2PYKDMTOH

Возьмем, скажем, букву H. Она встречается дважды: в позициях 02 (одна пробивка) и 7F (все пробивки). Таким образом, код 02 - первичный, а 7F - вторичный (его можно сделать, добавив пробивки, из любого кода).
Выяснение, какие 28 из 128 кодов используются как первичные, остается в качестве упражнения.

Tags:

Comments:

[User Picture]
From:alextr98
Date:January 14th, 2017 06:12 pm (UTC)
(Link)
А почему именно 28 символов?
Надо хотя бы 26 букв и десять цифр - 36 символов в алфавите.
Или задача стоит - сколько максимум можно закодировать таким образом в 7 битах? В 8 битах?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 14th, 2017 11:02 pm (UTC)
(Link)
Там по ссылке есть ссылка на патент 1982 года, в котором Ривест и Шамир пишут, что для 7-битных кодов они вручную нашли 26-символьный алфавит, смогли доказать что 29-символьного нет, а больше сказать не могут. Вот, наконец, точную верхнюю грань и построили.
Сколько можно в 8 битах, неизвестно. Я попытался погуглить имя мужика, который нашел 28-символьный алфавит, в надежде найти блог, в котором он про это подробно рассказывает - ничего хорошего не нашлось.
(Reply) (Parent) (Thread)