Max Home IndustryЕсли вы не занимаетесь теорией кодирования, вы, возможно, никогда не слышали об Эндрю Витерби, но на 100% уверены, что вы использовали его алгоритм декодирования.
Мне нужно кое в чем признаться. Когда я изучал теорию кодирования, был введен алгоритм Витерби, и мы потратили много времени на его изучение и даже реализацию. Однако по причинам, которые я не могу объяснить, я предположил, что это был старый алгоритм, известный в течение длительного времени и обновленный из-за эпохи электроники.
Я не мог ошибиться сильнее.
Эндрю Джеймсвитерби с женой Эмой
Алгоритм Витерби был изобретен в 1967 году Эндрю Джеймсом Витерби. Родившись в итальянском Бергамо, он переехал в США в 1938 году и сменил свое первоначальное имя Андреа на Эндрю. Витерби преподавал в UCLA и USCD и в настоящее время является профессором электротехники в инженерной школе Витерби Университета Южной Калифорнии, которая была названа в знак признания его подарка в размере 52 миллионов долларов.
Как мог профессор умудриться подарить столько денег?
Простой ответ заключается в том, что вместе с доктором Ирвином Джейкобсом он основал Qualcomm — да, компанию, которая, помимо всего прочего, производит чипы ARM. Первоначально Qualcomm начала создавать коммуникационные устройства, такие как мобильные телефоны и модемы.
Есть много инноваций, за которые отвечает Витерби, в том числе — CDMA, используемый мобильными телефонами повсюду, — но больше всего он известен алгоритмом Витерби.
Это декодер максимального правдоподобия для сверточных или решетчатых кодов. Сверточные коды были огромным прорывом, и они ответственны за создание более высокоскоростных акустических модемов, ADSL, спутниковой связи и вещания, мобильных телефонов и даже устройств хранения данных, таких как дисководы. Эти коды исправления ошибок могут использоваться для передачи данных по маломощным и зашумленным каналам с частотой ошибок в одну тысячную или выше, чем частота ошибок одного кодированного сигнала.
Алгоритм Витерби является декодером сверточных кодов и представляет собой приложение динамического программирования. В более общем плане алгоритм Витерби является оценкой максимального правдоподобия состояний скрытой цепи Маркова.
Сначала считалось, что алгоритм слишком сложен, чтобы быть практичным, но сегодня существуют программные и аппаратные реализации. Если вам не повезет, вы можете увидеть «Ошибку декодера Витерби» от спутникового приемника, если сигнал очень шумный. Возможно, этот алгоритм недостаточно известен в кругах разработчиков программного обеспечения, потому что он часто рассматривается как нечто связанное с аппаратным обеспечением. Вероятно, есть и другие приложения для этого, которые просто ждут, чтобы о них подумали. Удивительно, но алгоритм не был запатентован по совету адвоката. Как изменились времена!
Витерби получил множество наград за свою работу — в частности, Национальную медаль науки и Почетную медаль IEEE. Последняя, премия Чарльза Старка Дрейпера, присуждается в размере 500 000 долларов.
В цитате говорится;
«Эндрю Дж.Витерби разработал алгоритм Витерби как метод улучшения кода с исправлением ошибок, используемого в телекоммуникациях. Его публикация алгоритма в IEEE Transactions on Information Theory в 1967 году помогла вступить в эпоху сотовых телефонов, сосредоточив внимание только на наиболее вероятных вычислительных путях для телекоммуникационных сигналов, что в конечном итоге облегчило устранение статики в передачах. Алгоритм Витерби оказал наибольшее влияние на цифровые сотовые телефоны—будь то GSM, CDMA, TDMA, 3G или 4G LTE, все они используют по крайней мере один алгоритм Витерби для декодирования каналов,—но вскоре после его открытия он был использован в других приложениях, таких как кабельные, DSL-модемы и Ethernet. Алгоритм Витерби также сыграл важную роль в сигналах межпланетной связи, что позволило повысить уровень сигнала в дальних космических миссиях, таких как Mars Pathfinder, Mars Exploration Rover и зонд Кассини к Сатурну.”
Премия Дрейпера будет вручена на торжественном ужине в Вашингтоне, округ Колумбия, 16 февраля 2016 года.