Дмитрий Радищев (dibr) wrote,
Дмитрий Радищев
dibr

трельяж

Когда-то давно, когда модемы втыкались в обычный проводной телефон, и говорили в него "пшшш", рост скорости передачи данных упёрся в то, что даже имея заметный "запас по шумам", и относительно низкую вероятность неправильной передачи "символа(*)", вероятность того, что будет "убит" хотя бы один символ в пакете из нескольких десятков-сотен символов (короче делать пакет нет смысла, растёт оверхед) оказывается примерно в те самые десятки-сотни раз выше. А значит, скорость приходится занижать - и по сравнению с теоретическим пределом весьма заметно - чтобы протоколы коррекции (работающие по принципу перезапроса "битых" пакетов), не захлёбывались от этих самых ошибок.

Можно догадаться, что эта проблема решается избыточностью - ну, примерно как на компакт-дисках, где небольшой процент "нечитаемых" данных некритичен и полностью восстановим. Но разработчики протоколов модемов не стали брать готовый универсальный алгоритм добавления избыточности, а разработали новый (так называемое "треллис(**)-кодирование" на стороне передатчика и "декодер Витерби" в приёмнике), с учётом того факта, что при передаче "символов" по аналоговым линиям, "битый" символ скорее всего будет ошибочно продетектирован как соседний в сигнальном созвездии, а вероятности всех остальных ошибок на порядки ниже (и с ними справится вышележащий протокол коррекции). Матан там используется довольно зубодробильный (множество возможных путей в сигнальном созвездии прореживается так, чтобы некоторые пути считались "ошибочными", и для каждого "ошибочного" пути существовал единственный "истинный" путь, отличающийся от "ошибочного" одним (или более? не помню) символом, соседним "ошибочному" по сигнальному созвездию), но идея простая - поскольку мы заранее знаем, какие ошибки бывают часто ("ткнули не в нужную точку, а в соседнюю"), а какие - редко, мы можем заложиться на исправление только частых ошибок.

А сейчас я набираю sms на экранной клавиатуре смартфона (и регулярно промахиваюсь - стилусом на старом смартфоне с резистивным экраном, кстати, промахивался реже, хотя кнопки были меньше), а умная клавиатура это распознаёт, и подставляет правильные слова. При этом угадывая даже при двойных, а то и тройных, ошибках, при которых я и сам бы не догадался, что я набрать-то хотел. Иногда лажает, конечно, но реже чем можно было бы предположить.
И вот кажется мне, что без декодера Витерби тут не обошлось - должна же она учитывать то, что при промахе я обычно попадаю именно в соседнюю кнопку :-) (А потом я смотрю, как при длинной строке она начинает тормозить на четырёх ядрах по 1.5ГГц, и понимаю, что без Витерби как раз скорее всего обошлось - сделали полный перебор, и хватит - телефоны нынче мощные, мощнее некоторых десктопов)...

(*) "символ" - это не просто буква или байт, это специальный термин, обозначающий "точку в сигнальном созвездии" (сетке из используемых для модуляции точек в пространстве комплексной амплитуды при амплитудно-фазовой модуляции). В символе, теоретически, может быть даже нецелое число бит!

(**) "треллис", внезапно, переводится как "трельяж". А "трельяж" - это такая решётка, за которую цепляются вьющиеся растения. Кодирование назвали этим словом потому, что эти самые "пути по созвездиям" очень напоминали решётку, а Витерби - ну, просто мужик, который это придумал :-)
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments