Річард Хеммінга і початок теорії кодування

Марк Биховський

Людина -- винахідник і творець. Моральна совість людини повинна кожну мить життя проявляти творчість і винахідливість.

Микола Бердяєв

Вступ

У книзі Стефана Цвейга "Зоряні години людства" є чудовий оповідання "Геній однієї ночі "про офіцера французької армії Руже де Лілі, написані протягом однієї ночі в запалі охопила його натхнення знамениту "Марсельєзу". Це було в 1792 р. у революційному Марселі. Пісня протягом декількох днів поширилася по Франції, швидко набула колосальну популярність у всьому світі і згодом стала національним гімном Французької республіки. Історія зберегла ім'я Руже в пам'яті нащадків завдяки цій єдиній пісні.

За аналогією Річарда Хеммінга можна назвати "генієм однієї ідеї". Він сформулював її у 1950 р. у своїй єдиній науковій статті, присвяченій кодами для корекції помилок. Стаття містила конструкцію блочного коду, що коректує поодинокі помилки, які виникають при передачі повідомлень.

Річард Хеммінга постійно вів активні наукові дослідження, однак знаменитою стала його єдина робота в галузі теорії інформації, яка складає за своїм обсягом незначний відсоток його наукової творчості. Ця стаття швидко здобула світову популярність і принесла йому заслужену славу.

Подібно до того, як слідом за відкриттями Фарадея і Максвела послідували численні винаходи в галузі електрозв'язку, які змінили наше життя, так і після створення Клодом Шенноном теорії інформації та Володимиром Котельниковим теорії потенційної завадостійкості відкрилися нові можливості для розвитку телекомунікацій. Одним з найважливіших розділів теорії інформації є теорія кодування, основи якої були закладені Хеммінга.

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

Хеммінга був першим, хто запропонував конструктивний метод побудови кодів з надмірністю і простим декодуванням. Його праця визначив напрямок більшості робіт в цієї області, що сталися пізніше.

Коротка біографія

Річард Веслі Хеммінга народився 11 лютого 1915 р. в Чикаго. У 1937-му він закінчив Чиказький університет і отримав ступінь бакалавра. Він продовжив освіту в університеті штату Небраска, де в 1939 р. він отримав наступна -- магістерська ступінь. У 1942 р. Річард став доктором філософії в галузі математики в університеті штату Іллінойс.

У 1945-му Хеммінга брав участь у знаменитому Манхеттенському дослідницькому проекті, метою якого було створення атомної бомби.

А з 1946 р. в лабораторії Белла він починає займатися конструюванням комп'ютерів. У цьому знаменитому центрі, де працювали К. Шеннон і багато інших видатні вчені, йому судилося пропрацювати майже тридцять років.

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

Пионерская робота Хеммінга була відзначена багатьма нагородами. У 1968-му він став почесним членом Інституту інженерів з електротехніки та електроніки (IEEE) і був нагороджений премією Тьюрінга Асоціації комп'ютерних технологій. За винятковий внесок у розвиток інформаційних наук і систем у 1979 р. йому присуджено премію Еммануїла Піоро. У 1980-му його обрали членом Національної Академії інженерних наук, в 1981-му він отримав премію Гарольда Пендера від Пенсильванського університету, а в 1988-му - почесну медаль IEEE. У 1996 р. в Мюнхені за роботу за кодами, коригувальним помилки, Хеммінга був удостоєний престижної премії Едуарда Реймі в розмірі $ 130 000.

Помер Річард Хеммінга 7 січня 1998 у віці 82 років.

На його честь Інститут інженерів з електротехніки та електроніки заснував медаль, якою нагороджуються вчені, які внесли значний внесок у теорію інформації.

Роботи, що заклали основи теорії кодування

Коди, здатні коригувати помилки (в каналах зв'язку в цифрових обчислювальних машинах і т. п.) при обробці сигналів, були запропоновані Хеммінга ще до 1948 р., коли була опублікована відома стаття Шеннона "Математична теорія зв'язку", заклала міцну основу теорії в цій галузі.

У цій статті Шеннон, посилаючись на дослідження, виконане в 1947 р. його товаришем по службі по лабораторії Белла Річардом Хеммінга, описав як приклад простий код довжини 7, коригувальний всі поодинокі помилки. Публікація ж оригінальному матеріалу Хеммінга по патентних міркувань була затримана до квітня 1950-го. Слід зазначити, що приклад коригуючого помилки коду, наведений у згаданій статті Шеннона, ініціював дослідження іншого американського вченого, М. Е. Голі. Голей незалежно від Хеммінга відкрив коди, що коректують поодинокі помилки. У 1949 р. (тобто раніше Хеммінга) він опублікував коротку замітку (всього на півсторінки) про свої результати в Працях IЕЕE. У цій замітці він розглянув не тільки бінарні коди, але і коди загального вигляду, комбінації яких належать кінцевому полю (математичному безлічі елементів з певними операціями додавання, віднімання, ділення та множення) з Рn елементами (р - просте, а n - ціле число).

Треба відзначити, що ряд основних ідей теорії зв'язку був відомий як приватних математичних результатів ще до того, як їх почали застосовувати вчені, які вирішують проблеми передачі повідомлень по каналах зв'язку. У своїй книзі "Алгебраїчна теорія кодування "великий американський фахівець у галузі теорії кодування Е. Берлекамп зробив дуже цікаве зауваження. Він зазначив, що конструкція кодів Хеммінга була описана в іншому контексті ще в 1942 р. відомим американським математиком Р. А. Фішером, в роботі присвяченій теорії факторного аналізу (одного з розділів математичної статистики) і її зв'язку з математичної теорією груп. До речі, теорема В. А. Котельникова, що вказує на можливість подання аналогових сигналів в цифровому вигляді, теж була відкрита як один з приватних математичних результатів теорії інтерполяції функції ще на початку ХХ століття англійськими математиками Е. Т. і Дж. М. Уіткерамі. Слід підкреслити, що ні Фішер, ні згадані англійські вчені не пов'язували свої результати з найважливішими для сучасного світу проблемами передачі інформації по каналах зв'язку.

Вольфганг Гете говорив: "Недостатньо лише отримати знання, треба знайти йому програму. Недостатньо тільки бажати, треба робити ". Для теорії і техніки зв'язку теорема Котельникова та коди Хеммінга мають виняткове значення, оскільки саме завдяки їм перед інженерами відкрилася ясна перспектива створення цифрових систем, які в кінці ХХ століття зробили революцію в електрозв'язку і тому їх з повною підставою називають іменами цих вчених.

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

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

У цьому вираженні кількість помилок e може бути виправлено коригувальним блоковим кодом завдовжки N, що мають М кодових комбінацій (CjN - Біноміальний коефіцієнт).

Робота Хеммінга зіграла ключову роль у подальшому розвитку теорії кодування і стимулювала великі дослідження, виконані в наступні роки. У 1956 р. Давид Сліпучий першим виклав теорію кодів з перевіркою парності на серйозної математичної основі. Головний зрушення в галузі теорії кодування стався, коли французький вчений А. Хоквінгем (1959 р.) та американці Р. К. Боуз і Д. К. Рой-Чоудхурі (1960 р.) знайшли великий клас кодів (коди БЧХ), що виправляють кратні помилки. Американські дослідники І. С. Рід та Г. Соломон (1960 р.) знайшли пов'язаний з кодами БЧХ клас кодів для Недвійкова каналів.

У 1980 р. Хеммінга написав блискучий підручник "Теорія кодування та теорія інформації", який в 1983 р. був переведений на російську мову. Цю книгу, як і інші його праці, відрізняє оригінальність постановки питань, популярність викладу, глибоке розуміння практичних завдань, коректність і розумна ступінь строгості математичної трактування порушених питань. Виклад матеріалу побудовано таким чином, що читачеві інтуїтивно зрозуміло, чому справедлива та чи інша теорема.

Висновок

Річард Хеммінга володів найширшої ерудицією. До сфери його наукових інтересів входив великий коло математичних і технічних проблем. Він отримав першокласні результати не тільки в теорії кодування, але і в ряді інших галузей науки.

У 1956 р. Хеммінга, працюючи над створенням одного з перших комп'ютерів IBM 650, запропонував мова програмування високого рівня, який застосовується і сьогодні. Цікаві його дослідження в області чисельних методів вирішення різного роду прикладних математичних задач. Він створив нові методи чисельної інтеграції диференціальних рівнянь і спектрального аналізу і запропонував використовувати для згладжування даних при спектральному аналізі вікно Хеммінга, що дозволяє здійснювати їх попередню ефективну фільтрацію, рятуючи від помилок вимірювань.

Хеммінга прославився не тільки як вчений, але і як видатний педагог. Висловлюючись словами Бердяєва, винесених в епіграф до цього нарису, він "кожну мить життя виявляв творчість і винахідливість ". З 1962 по 1997 рр.. їм написано вісім книг по прикладних чисельних методів аналізу, цифрових фільтрів, теорії кодування і теорії інформації, теорії ймовірностей і математичної статистиці. У книгах проявилося велике наукове та педагогічне обдарування автора, і вони внаслідок їх дивовижної ясності користувалися величезною популярністю. Три його праці (з чисельних методів аналізу, цифрових фільтрів і по теорії кодування та теорії інформації) були видані в Росії.

Створюючи ці чудові книги, Хеммінга бачив своє завдання не тільки в тому, щоб фахівці отримали глибокі знання, він прагнув до того, щоб вони відчули сам дух науки. Його девізом було: "Мета розрахунків - не числа, а розуміння ".

У своїй останньої досить цікавій книзі "Мистецтво наукового дослідження і винаходи: вчитися вивчати ( "The Art of Doing Science and Engineering: Learning to Learn "), виданої в 1997 р., Хеммінга виклав філософські погляди на природу і принципи наукової творчості.

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://www.computer-museum.ru/