Двійковий код та винекнення кодування

Коди з'явилися в глибокій старовині у вигляді криптограми (по-грецьки - тайнопису), коли ними користувалися для засекречування важливого повідомлення від тих, кому воно не було призначене. Вже знаменитий грецький історик Геродот (V століття до н. Е.) Наводив приклади листів, зрозумілих лише для одного адресата. Спартанці мали спеціальний механічний прилад, за допомогою якого важливі повідомлення можна було писати особливим способом, що забезпечує збереження таємниці. Власна секретна абетка була у Юлія Цезаря. В середні віки і епоху Відродження над винаходом таємних шифрів трудилися багато видатних людей, в їх числі філософ Френсіс Бекон, великі математики Франсуа Вієт, Джироламо Кардано, Джон Валліс.

З плином часу почали з'являтися по-справжньому складні шифри. Один з них, який вживається і понині, пов'язаний з ім'ям ученого абата з Вюрцбурга Трітеміуса, якого до занять криптографією спонукало, можливо, не тільки монастирське усамітнення, а й потреба зберігати від розголосу деякі духовні таємниці. Різні хитромудрі прийоми кодування застосовували шифрувальники при папському дворі і дворах європейських королів. Разом з мистецтвом шифрування розвивалося і мистецтво дешифрування, або, як кажуть, криптоанализа.

Секретні шифри є невід'ємною приналежністю багатьох детективних романів, в яких діють витончені в хитрості шпигуни. Письменник-романтик Едгар По, якого іноді зараховують до творців детективного жанру, в своїй розповіді "Золотий жук" в художній формі виклав найпростіші прийоми шифрування і розшифровки повідомлень. Едгар По ставився до проблеми розшифровки оптимістично, вклавши в уста свого героя наступну фразу: "... чи розуму людини дано загадати та кую загадку, яку розум іншого його побратима, спрямований належним чином, не зміг би розкрити. Прямо скажу, якщо текст зашифрований без грубих помилок і документ в пристойній збереження, я більше ні в чому не потребую; наступні труднощі для мене просто не існують ". Століття по тому це висловлювання було спростовано вченим, що заклав основи теорії інформації, Клодом Шенноном. Шеннон показав, як можна побудувати криптограму, яка не піддається ніякої розшифровці, якщо, звичайно, ніхто не знає спосіб її складання.

Про деякі прийоми криптографії та криптоаналізу ми розповімо в наступному параграфі, в інших частинах книги мова буде йти в основному про іншому напрямку в кодуванні, яке виникло вже в найближчу нам епоху. Пов'язане воно з проблемою передачі повідомлень по лініях зв'язку, без яких (т. Е. Без телеграфу, телефону, радіо, телебачення і т. Д.) Немислимо наше нинішнє існування. У завдання такого кодування, як уже говорилося, входить аж ніяк не засекречування повідомлень, а інша мета: зробити передачу повідомлень швидкої, зручної та надійної. Призначене для цієї мети кодує пристрій зіставляє кожному символу переданого тексту, а іноді і цілим словами або фразами (повідомленнями) певну комбінацію сигналів (прийнятну для передачі по даному каналу зв'язку), звану кодом або кодовим словом. При цьому операцію перекладу повідомлень в певні послідовності сигналів називають кодуванням, а зворотну операцію, що відновлює по прийнятим сигналам (кодовою словами) передаються повідомлення, - декодуванням.

Зауважимо відразу ж, що різні символи або повідомлення повинні кодуватися різними кодовими словами, в іншому випадку по кодовою словами не можна було б відновити передані повідомлення.

Історично перший код, призначений для передачі повідомлень, пов'язаний з ім'ям винахідника телеграфного апарату Семюеля Морзе і відомий всім як азбука Морзе. У цьому коді кожної букви або цифри зіставляється своя послідовність з короткочасних (званих точками) і тривалих (тире) імпульсів струму, що розділяються паузами. Інший код, так само широко поширений в телеграфії (код Бодо), використовує для кодування два елементарних сигналу - імпульс і паузу, при цьому зіставляються буквах кодові слова складаються з п'яти таких сигналів.

Коди, що використовують два різних елементарних сигналу, називаються двійковими. Зручно буває, відволікаючись від їх фізичної природи, позначати ці два сигнали символами 0 і 1. Тоді кодові слова можна представляти як послідовності з нулів і одиниць.

Двійкове кодування тісно пов'язане з принципом дихотомії (ділення навпіл). Пояснимо цей принцип на прикладі.

Хтось задумав число, укладену між 0 і 7. вгадувати дозволено ставити запитання, відповіді на які даються лише в формі "так" або "ні". Яким чином слід задавати питання, щоб якомога швидше дізнатися задумане число?

Самий нехитрий шлях - перебирати числа в будь-якому порядку, сподіваючись на удачу. В цьому випадку при везінні може вистачити і одного питання, але якщо не пощастить, то може знадобитися і цілих сім. Тому не будемо розраховувати на везіння і постараємося побудувати таку систему питань, щоб будь-який з відповідей - "так" або "ні" - давав нам однакову (нехай спочатку і неповну) інформацію про задуманому числі. Наприклад, перше питання може бути таким: "Укладено задумане число в межах від 0 до 3?" Обидва відповіді - і "так" і "ні" - однаково наближають нас до мети: в будь-якому випадку залишаються чотири можливості для невідомого числа (а спочатку їх було вісім).

Якщо на перше питання отримано позитивну відповідь, то вдруге можна запитати: "Чи не є задумане число нулем або одиницею?"; якщо ж відповідь була негативною, запитаємо: "Чи не є задумане число четвіркою або п'ятіркою"? У будь-якому випадку після відповіді на друге питання залишиться вибір з двох можливостей. Для того щоб його здійснити, досить одного питання. Отже, для вгадування задуманого числа, яким би воно не було, досить трьох питань (кожен з них з'ясовує, чи міститься задумане число в "нижній" половині укладає його проміжку). Можна показати, що меншого числа питань недостатньо. 

Якщо можливі відповіді "так" або "ні" позначити умовно символами 0 і 1, то відповіді запишуться у вигляді послідовності, що складається з нулів і одиниць. Так, наприклад, якщо задумане число було нулем, то на кожен з трьох питань відповіддю буде «так». Трьом "так" відповідає послідовність 000.

Якщо було задумано число 3, то відповідями будуть "так", "ні", "ні", т. Е. Кількістю 3 відповідає послідовність 011.

Читач, знайомий з двійковій системою числення, дізнається в нижньому рядку двійкову запис відповідних чисел верхнього рядка.

Зауважимо, що замість безлічі чисел від 0 до 7 можна розглядати будь-яка множина з восьми повідомлень, і кожне з них ми можемо закодувати послідовностями з нулів і одиниць довжини 3. Якщо використовувати довші виконавчі послідовності, то ними в принципі можна закодувати будь-яке кінцеве безліч повідомлень .

Дійсно, число двійкових послідовностей довжини 3 дорівнює 23 = 8 (всі вони наведені в таблиці 1), довічних послідовностей довжини 4 вдвічі більше - число їх одно 24 = 16. Взагалі, число двійкових послідовностей довжини n одно 2n. Тому, якщо потрібно закодувати нулями і одиницями, наприклад, 125 повідомлень, то для цього з надлишком вистачить довічних послідовностей довжини 7 (їх в нашому розпорядженні є 27 = 128). З цього прикладу стає ясно, що М повідомлень можна закодувати двійковими послідовностями довжини п тоді і тільки тоді, коли виконується умова 2n ≥ М, т. Е. Коли n ≥ log2M.

Перший, хто зрозумів, що для кодування досить двох символів, був Френсіс Бекон. Двійковий код, який він використовував в криптографічних цілях, містив пятіразрядний (як і в коді Бодо) слова, складені з символів 0, L.

Думка про двійковій системе Належить Лейбніца, Який вважать, что при Важко дослідженнях в Теорії чисел вона может мати Великі Преимущества перед десятковою системою. Кроме того, при будь-якіх Арифметичний операціях Дії над числами, написання в бінарній системе, полегшуються Надзвичайно. Єзуїт Буве (Bouvet), Місіонер в Китаї, з Яким Лейбніц писав про свой Винахід, сообщил Йому, что в Китаї існує Загадковий напис, якові можна Цілком поясніті бінарної системою. Напис ця, якові пріпісують імператору Фо-ги, что живий в 25 столітті до н. е., засновнику китайської імперії, покровителю наук і мистецтв, не могла буті пояснена Китайський вчений, Які вважаю ее НЕ має СЕНС. Вона складається з ряду довга і коротких рисок. Если Прийняти, что довга рису означає 1, а коротка 0, то вся напис віявляється просто поруч натуральних чисел, написання по двійковій системе.

Двійкова система числення виявило Зручне для использование в ЕОМ. Використання двійкової системи виявило найбільш ефективних в електронною схеми: Цифри 0 и 1 Зручне кодуваті рівнямі напруги, відповіднім напрузі на шинах харчування, "0" і "+ V"; использование більшої кількості рівнів прізвело б до ускладнення схем. Хоча були прецеденти создания и потрійніх ЕОМ, зокрема Сетунь.

Двійковий запис чисел

У двійковій системі числення числа записуються за допомогою двох символів (0 і 1). Щоб не плутати, в якій системі числення записано число, його постачають покажчиком справа внизу. Наприклад, число в десятковій системі 510, в двійковій 1012. Іноді двійковечисло позначають префіксом 0b або символом & (амперсанд) [1], наприклад 0b101 або відповідно & 101.

У двійковій системі числення (як і в інших системах числення, крім десяткового) знаки читаються по одному. Наприклад, число 1012 вимовляється «один нуль один».