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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

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

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

Введення

У книзі Стефана Цвейга "Зоряні години людства" є чудовий розповідь "Геній однієї ночі" про офіцера французької армії Руже де Лілі, який написав протягом однієї ночі в запалі охопила його натхнення знамениту "Марсельєзу". Це було в 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 р., Хеммінга виклав філософські погляди на природу і принципи наукової творчості.

Додати в блог або на сайт

Цей текст може містити помилки.

Історія та історичні особистості | Реферат
24.3кб. | скачати


Схожі роботи:
Практичне кодування по Хеммінга
Метод словникового кодування Зеева Лемпела Диференціальне кодування
Метод словникового кодування Зеева-Лемпела Диференціальне кодування
Арифметичне кодування Кодування довжин повторень
Нейронна мережа Хеммінга
Річард Рорті
Річард Бендлер
Сучасні японські історики про освоєння Південно-Курильських островів початок XVII - початок XIX століття
Літературний герой РІЧАРД II
© Усі права захищені
написати до нас