Что такое код getdrivername

Содержание

Синдромное декодирование линейных блочных кодов

Читайте также:

  1. I.1. Общая характеристика нелинейных систем
  2. I.2.Примеры нелинейных систем управления
  3. АВТОМАТИЗИРОВАННОЙ ИДЕНТИФИКАЦИИ ШТРИХОВЫХ КОДОВ
  4. Вес и расстояние Хемминга. Способность кодов обнаруживать и исправлять ошибки
  5. Виды систем линейных уравнений
  6. Геодезические работы при проектировании изысканий сооружений линейного типа (нивелирование трасс линейных сооружений)
  7. Графические методы расчета нелинейных цепей постоянного тока
  8. Декодирование информации циклическими кодами
  9. Декодирование методом максимального правдоподобия
  10. Декодирование сверточных кодов. Алгоритм Витерби
  11. Декодирование сообщений
  12. Измерение линейных и угловых ускорений

Покажем, как можно использовать синдром принятого вектора не только для обнаружения, но и для исправления ошибок.

Пусть U = ( U , U1 , …, Un-1 ), e = ( е , е1, …, еn-1 ) и r = ( r , r1, r2 , …, rn-1) являются передаваемым кодовым словом, вектором-ошибкой и принятым вектором соответственно. Тогда

r = U + e (3.25)

S = r×H T = (U + e )× H T = U× H T + e× H T = 0 + e× H T = e× H T , (3.26)

поскольку для любого кодового слова U × H T = 0.

Таким образом, синдром принятой последовательности r зависит только от ошибки, имеющей место в этой последовательности, и совершенно не зависит от переданного кодового слова. Задача декодера, используя эту зависимость, определить элементы (координаты) вектора ошибок. Найдя вектор ошибки можно восстановить кодовое слово как

U* = r + e . (3.27)

На примере одиночных ошибок при кодировании с использованием линейного блочного (7,4)-кода покажем, как вектор ошибки связан с синдромом, и как, имея синдром, локализовать и устранить ошибки, возникшие при передаче.

Найдем значения синдрома для всех возможных одиночных ошибок в последовательности из семи символов:

e_ = ( 0000000 ),

T
e_ × H T = ( 0000000 ) × = (000);

e = ( 1000000 ),

T
e× H T = ( 1000000 ) × = (110);

e1 = ( 0100000 ),

T
e1× H T = ( 0100000 ) × = (011);

e2 = ( 0010000 ),

T
e2× H T = ( 0010000 ) × = (111);

e3 = ( 0001000 ),

T
e3× H T = ( 0001000 ) × = (101);

e4 = ( 0000100 ),

T
e4× H T = ( 0000100 ) × = (100);

e5 = ( 0000010 ),

T
e5× H T = ( 0000010 ) × = (010);

e6 = ( 0000001 ),

T
e6× H T = ( 0000001 ) × = (001).

Все возможные для (7,4)-кода одиночные ошибки и соответствующие им векторы синдрома приведены в табл. 3.3.

Вектор ошибки Синдром ошибки Десятичный код синдрома

Из этой таблицы видно, что существует однозначное соответствие между сочетанием ошибок (при одиночной ошибке) и его синдромом, то есть, зная синдром, можно совершенно однозначно определить позицию кода, в которой произошла ошибка.

Например, если синдром, вычисленный по принятому вектору, равен ( 111 ), это значит, что произошла одиночная ошибка в третьем символе, если S = ( 001 ) – то в последнем, и т.д.

Если место ошибки определено, то устранить ее уже не представляет никакого труда.

Полная декодирующая схема для (7,4)-кода Хемминга, использующая синдром вектора r не только для обнаружения, но и для исправления ошибок, приведена на рис. 3.6.

А теперь посмотрим, что произойдет, если в принятой последовательности будет не одна, а, например, две ошибки. Пусть ошибки возникли во второй и шестой позициях e = ( 0100010 ). Соответствующий синдром определится как

S = ( 0100010 ) = (001).

Однако синдром S = ( 001 ) соответствует также и одиночной ошибке в седьмой позиции ( e6 ). Следовательно, наш декодер не только не исправит ошибок в позициях, в которых они произошли, но и внесет ошибку в ту позицию, где ее не было. Таким образом, видно, что (7,4)-код не обеспечивает исправления двойных ошибок, а также ошибок большей кратности.

Это, однако, обусловлено не тем, каким образом производится декодирование, а свойствами самого кода. Несколько позднее будет показано, от чего зависит исправляющая способность кода, то есть сколько ошибок он может исправить.

Дата добавления: 2014-01-07 ; Просмотров: 1619 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Сверточные коды

Кодирующее устройство двоичного сверточного кода (рис. 1.16) представляет собой регистр сдвига, состоящий из k ячеек, к выходам которых в определенном порядке подключены п сумматоров по модулю 2. Двоичные информационные символы, поступающие в регистр от источника информации, сдвигаются в регистре на q

Если для каждой ветви кодового дерева в выходной последовательности символов присутствуют без изменений входные символы, породившие эту ветвь, то сверточный код называется систематическим. В противном случае код называется несистематическим.

Для декодирования сверточных кодов разработан ряд эффективных методов декодирования, в частности, последовательное декодирование и декодирование А. Витерби .

Принцип последовательного декодирования в двоичном дискретном канале состоит в следующем, п регенерированных символов сверточного кода, соответствующих одной из ветвей кодового дерева, на приемной стороне записывается в регистр сдвига. Декодирующее устройство, аналогичное кодирующему устройству данного сверточного кода, генерирует п символов сверточного кода, соответствующих каждой из ветвей кодового дерева, исходящей из данного узла. Каждая из двух последовательностей п символов, генерируемых в декодирующем устройстве, поразрядно суммируется по модулю 2 с принятой последовательностью, записанной в регистре. В результате этих операций вычисляется расстояние Хэммннга dХ между этими последовательностями и принятой последовательностью. Затем выбирается путь с наименьшим dХи выносится предварительное решение, что путь по данной ветви кодового дерева и является истинным. Расстояние dХ для этого пути запоминается, и декодирующее устройство переходит к следующему узлу кодового дерева, к которому при водит выбранный путь. Из этого нового узла вновь исследуются два возможных пути п т. д.

Если вероятность искажения одного символа шумами при передаче равна p, то математическое ожидание числа ошибок, а следовательно, и расстояние Хэмминга dХ. между принятыми п символами сверточного кода и п символами, соответствующими правильному пути по данной ветви кодового дерева, будет равно пр.

Если же по данной ветви выбран неправильный путь, то математическое ожидание расстояния dX для него будет приблизительно равно n/2. Следовательно, через l последовательных шагов декодирования математическое ожидание dx(l) для правильного пути будет равно lпр, а для неправильного пути ln/2. Действительные значения dx(l) для правильного п неправильного пути будут случайными величинами с указанными математическими ожиданиями. Это показано на рис. 1.19.

Рис. 1.19. Зависимостькодового расстояния для правильного и неправильного путей.

В последовательном декодирующем устройстве сравнивается текущее значение dx(l) с некоторым порогом z(l) (рис. 1.19). Если на текущем шаге декодирования порог не превышен, то декодирующее устройство переходит к анализу путей, ведущих из следующего узла. Если порог превышен, то декодирующее устройство возвращается в прошлый узел, для которого не было превышения порога, и исследует другие возможные пути по. кодовому дереву. Таким образом, декодирующее устройство обследует все доступные узлы до тех пор, пока не найдется пути, при котором текущий порог z(t) не превышается. Если же такого пути не находится, то порог повышается и указанная операция повторяется.

Поскольку связи между символами на выходе сверточного кодирующего устройства, имеющего k-разрядный регистр сдвига, распространяются на k ветвей кодового дерева, то, найдя один из путей по k ветвям дерева, удовлетворяющий установленному порогу, декодирующее устройство выносит окончательное решение о декодировании первой ветви, соответствующей этому пути. Далее так же декодируется вторая ветвь дерева, и т. д. В таком процессе ошибка при декодировании произойдет, если неправильный путь по кодовому дереву не будет обнаружен на протяжении k последовательных ветвей.

Достоинством последовательного декодирования является то, что при исключении какого-либо пути по кодовому дереву отбрасываются все другие пути, исходящие из узлов исключенного. За счет этого экономится число операций, производимых при декодировании. Чем выше порог z(l), тем большее количество операций требуется, так как неправильный путь, начавшийся из некоторого узла, обнаруживается позднее. Поэтому сначала декодирование ведут при низком (жестком) пороге; при этом пороге декодируется большинство символов сверточного кода. Если же путей, удовлетворяющих этому порогу, не находится (а это случается значительно реже) порог повышают.

Хотя среднее число операций на один декодированный символ, производимых. при последовательном декодировании, невелико, фактическое число операций величина случайная, меняющаяся в широких пределах. Эта неравномерность вычислительной нагрузки является недостатком последовательного декодирования. Кроме того, в случаях, когда происходит длительный поиск правильного пути по кодовому дереву, возможно переполнение регистра, в котором записываются принимаемые символы сверточного кода.

Рассмотрим теперь принципы декодирования сверточных кодов по методу Витерби. Для этого вновь рассмотрим кодирующее устройство сверточного кода, изображенное на рис, 1.17. В рассматриваемом случае выходные символы сверточного кода, появляющиеся после каждого цикла опроса коммутатором сумматоров по модулю 2, определяются тремя последовательно поступившими информационными символами, записанными в регистре перед опросом коммутатора, или, что то же, состоянием 2-х первых ячеек регистра и последним ступившим символом. Учитывая это, изобразим кодовое дерево, соответствующее этому кодирующему устройству, в несколько другом по сравнению с рис. 1.18 виде.

На рис. 1.20 четыре возможных состояния первых двух ячеек регистра сдвига кодирующего устройства обозначены цифрами 00, 01, 10, 11, заключенными в рамку. По приходе на кодирующее устройство очередного информационного символа первые две ячейки регистра меняют свои состояния. Если приходящий информационный символ «1», то возможный переход состояния показан пунктирной линией, если «0» — то сплошной линией. Цифрами 1, 2, 3 . обозначены тактовые моменты прихода на кодирующее устройство информационных символов

Рис. 1.20. Другой вид кодового дерева сверточного кода.

В исходном состоянии, соответствующем такту с номером 0, в регистре записаны нули. Выходные символы сверточного кода, порождаемые приходящим информационным символов, показаны около соответствующих переходов.

Из рис. 1.20 следует, что, начиная с третьего такта, структура кодового дерева повторяется, и каждое из 4 возможных состояний регистра определяется только двумя предшествующими состояниями. Например, состояние 01 на третьем такте имеет два входных пути по кодовому дереву, соответствующих информационным символам 110 и 010. Эти пути разошлись в такте 0 и слились в такте 3. В общем случае, если регистр кодирующего устройства содержит k ячеек и информационные символы перед каждым опросом коммутатора сдвигаются на q ячеек, то структура кодового дерева повторяется через k тактов, а пути сливаются через q(k-1) последовательно поступающих одинаковых информационных символов.

Для двоичного симметричного канала без памяти задачей оптимального декодирующего устройства, работающего по максимуму правдоподобия, является выбор такого пути по кодовому дереву, который имеет минимальное расстояние Хэмминга от принимаемой последовательности символов сверточного кода. Поскольку ветви дерева сливаются, то для декодирования по максимуму правдоподобия нет необходимости рассматривать всю полученную последовательность символов сверточного кода. Сразу после k-гo такта (на рис. 1.20 после 3-го такта) можно решить, какой один из 2 q путей, ведущих в данное состояние, наиболее правдоподобен, а остальные пути исключить из дальнейшего рассмотрения. Это делается для каждого из 2 q ( k -1) состояний в данном такте. Затем декодирующее устройство переходит к следующему такту и процесс повторяется.

Рассмотрим, например, состояние 01 на третьем тракте (рис. 1.20). К этому состоянию ведут два пути по кодовому дереву: первый путь 110101, соответствующий информационным символам 110, и второй путь 001110, соответствующий информационным символам 010. Пусть, например, получена последовательность символов сверточного кода 000110. Эта последовательность имеет расстояние Хэмминга dx=4 от первого пути и dx=1 от второго пути, и следовательно, первый путь можно исключить из дальнейшего рассмотрения.

Если окажется, что оба пути, ведущие в данное состояние, имеют одинаковое расстояние Хэмминга от принятой последовательности, т. е. они сливаются, то выбирается любой случайным образом и дальнейшие принимаемые символы никакой дополнительной информации об этих путях не дадут.

Описанное декодирование называется декодированием по методу Витерби. Таким образом, при декодировании по методу Витерби декодирующее устройство хранит в памяти множество из 2 q ( k -1) наиболее вероятных путей на каждом шаге декодирования. Окончательный выбор одного, наиболее вероятного пути, может осуществляться посредством передачи в конце сообщения, состоящего из N информационных символов, k-q заранее известных символов (например нулей, которые приводят декодирующее устройство в исходное состояние).

Как последовательное декодирование, так и декодирование но методу Витерби перспективно для использования в каналах с независимыми ошибками. Количество операций, необходимое для декодирования по методу Витерби N информационных символов, равно N/2 q ( k -1) Сложность декодирующего устройства, оцениваемая числом необходимых при декодировании операций, линейно зависит от N, что является достоинством этого метода. Однако количество операций экспоненциально зависит от k, поэтому этот метод используется лишь для относительно небольших k. Для всех сверточных кодов увеличение k, подобно увеличению длины кодового слова при блочном кодировании, при прочих равных условиях ведет к экспоненциальному уменьшению вероятности ошибки при декодировании. Поскольку сложность, последовательного декодирования мало зависит от k, его целесообразно применять при малых вероятностях ошибки на декодированный символ (р≤10 -3 -10 -5 [105]). При больших вероятностях ошибки целесообразно декодирование по методу Витерби.

Особенностью сверточных кодов является то, что при их декодировании не нужна синхронизация перед началом передачи информации, тогда как для блочных кодов без синхронизации по словам правильное декодирование в большинстве случаев невозможно. Действительно, декодирующее устройство, несинхронизированное перед началом передачи, эквивалентно синхронизированному, но сделавшему одну или несколько ошибок. Моделирование показало, то через (3-5)k синхронизация устанавливается автоматически. Однако для этого требуется надежная синхронизация узлов кодового дерева, т. е. синхронизация по группам символов, соответствующих одному циклу опроса коммутатора сумматоров по модулю 2 в кодирующем устройстве сверточного кода.

Не нашли то, что искали? Воспользуйтесь поиском:

Код Хэмминга (7; 4)

Всем привет! Сегодня я хочу рассказать вам немного о коде Хэмминга (7; 4). Этот простейший код может быть с лёгкостью применён любым человеком для передачи самокорректирующихся сообщений , и сегодня я хочу вам показать как именно этот код можно легко и просто использовать.

Структурно слова кода Хэмминга состоят из двух частей. Сначала идут информационные 4 бита, затем три бита проверочных. Будем обозначать информационные биты буквами ABCD, проверочные буквами xyz.

Таким образом слово кода Хэмминга имеет следующую структуру:

Для передачи 4 бит информации нам требуется передавать кодовое слово из целых 7 бит! Последние три бита в случае, когда ошибки отсутствуют, не несут никакой новой информации, ибо они зависят от первых 4. Однако если в кодовом слове из 7 бит произошла 1 ошибка, то исходные информационные 4 бита всё равно можно будет восстановить точно! В этом и состоит главная особенность самокорректирующихся кодов.

Естественно, использование кода Хэмминга при передаче данных требует увеличенных ресурсов. Здесь есть такое важное понятие как скорость кода — отношение числа информационных бит к общему числу бит. В случае кода Хэмминга скорость равна 4/7. Т.е., к примеру, чтобы передавать информацию со скоростью 1 Мбит/сек и коррекцией ошибок с помощью кода Хэмминга вам потребуется канал с пропускной способностью минимум в 7/4=1.75 Мбит/сек.

Для подсчёта проверочных бит можно использовать следующие формулы:

x = A + B + C mod 2,

y = A + B + D mod 2,

z = A + C + D mod 2,

где n mod 2 означает остаток от деления числа n на 2.

К примеру, если информационный вектор есть ABCD = 1001, то кодовый вектор будет ABCDxyz = 1001 100

Вместо непонятных формул можно использовать следующую картинку:

Здесь всё очень просто. Подставляете вместо букв значения соответствующих битов и затем считаете значения x, y и z как сумму по модулю 2 тех информационных бит, которые есть в соответствующем круге.

В приведённом выше примере будет:

Куда более интересным является вопрос об исправлении ошибок. Очевидно, вывод об отсутствии ошибок приёмник может сделать просто взяв информационные биты ABCD, посчитав на их основе проверочные биты xyz и сравнить посчитанные проверочные биты с принятыми. Если есть ошибка, то часть проверочных битов не совпадёт.

Предположим что произошла ошибка в проверочном бите y и было принято слово 1001 110

В таком случае два проверочных бита сойдутся, а один нет. Этого вполне достаточно чтобы сделать вывод что нужно исправить бит y (для которого проверка не сошлась).

Предположим, что произошла ошибка в одном из информационных битов BCD — к примеру в бите B.

В таком случае не сойдутся аж два проверочных бита — x (он равен 1, а «должен» равняться 0) и y. Посмотрев на круги легко увидим что они пересекаются по битам B и A. Т.к. не сошлось две проверки, то берём бит B (расположенный на пересечении двух проверок).

Наконец, отдельно рассмотрим бит A. Если в нём ошибка, то у нас не сойдутся все три проверки:

Увидев такое безобразие сразу же делаем вывод о том, что ошибка в бите A.

Таким образом, можно легко и просто вычислять локацию ошибки и исправлять её. Замечу что если ошибок больше одной, то описанный выше алгоритм сработает неверно. К примеру, допустим что произошли ошибки в битах C и z:

Проверочные биты y и z сойдутся, а бит x нет. Алгоритм исправит бит x и всё. Это вполне естественное поведение, т.к. если вероятность ошибки p 0).

Естественно, работать с цветными кругами удобно человеку, но неудобно компьютеру. У кодов Хэмминга есть одна особенность, которая позволяет их лёгкое декодирование на компьютере. Итак, рассмотрим следующий алгоритм:

Определим числа g, b, r как сумму всех четырёх бит в кругах соответствующего цвета. Т.е.:

g = A + B + C + x mod 2,

b = A + B + D + y mod 2,

r = A + C + D + z mod 2.

Фактически каждый из этих бит можно определить как сумму соответствующего проверочного бита, вычисленного на основании принятых информационных бит, с принятым проверочным битом. Т.е. к примеру g есть сумма (A + B + C mod 2) (по этой формуле считался x на стороне передатчика) и принятого x. Аналогично b соответствует y, r соответствует z.

Если ошибок нет, то gbr = 000 (принятые проверочные биты сошлись с вычисленными на основе информационного вектора).

Если же есть 1 ошибка, то число gbr есть номер (в двоичной записи) ошибочного бита в векторе ABCxDyz.

В качестве примера рассмотрим уже знакомый нам вектор ABCDxyz = 1001 100, в котором произошла ошибка в бите x (четвёртый бит в векторе ABCxDyz). Посчитаем gbr:

gbr = 100 [2] = 4 [10]. Ошибка в 4 бите, которым и является x. Таким образом, для декодирования и исправления ошибки в кодовом слове длины 7 требуется лишь вычислить три суммы и из полученного числа несложной функцией получить местонахождение ошибки.

Кодер и декодер кода Хэмминга на VB.NET

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

1 Что такое код Хэмминга

Код Хэмминга добавляет к сообщению (информационные разряды) некоторое количество избыточной информации (проверочные разряды), сформированной определённым образом. Сообщение с добавленной проверочной информацией называется «кодовый символ» или «кодовое слово». Параметры кода указываются, например, так: (7, 4). Это означает, что длина кодового слова равна 7 битам, а длина сообщения – 4 бита. В зависимости от количества информационных и проверочных разрядов в кодовых словах существуют коды Хэмминга (7,4), (9,5), (11, 7), (15, 11), (31, 26), (63, 57) и т. д.

Общий вид формулы, по которой определяются виды кодов Хэмминга по соотношению числа информационных символов к проверочным: (2 x − 1, 2 x − x − 1), где x – натуральное число.

Чтобы восстановить закодированное сообщение, оно подвергается декодированию. При этом есть вероятность, что исходное сообщение нельзя будет восстановить, в случае превышения числом ошибок корректирующей способности кода. Однако помехоустойчивость закодированной информации всё равно выше, чем у незакодированной.

Из-за своей простоты, кодирование кодом Хемминга получило широкое распространение. Оно применяется, например, в беспроводной технологии WiFi, в системах хранения данных (RAID-массивах), в некоторых типах микросхем памяти, в схемотехнике и т.д.

Хорошая статья, описывающая принцип работы кода Хэмминга, есть, например, на Хабре.

2 Кодер кода Хэмминга (15, 11), написанный на VB.NET

Напишем кодировщик, который будет получать на вход 11 бит данных, кодировать их и возвращать 15 бит выходной информации. Если на вход пришло больше 11-ти бит данных, генерируется исключение. Если данных меньше 11-ти бит (например, 1 байт – 8 бит), то число дополняется нулями в старших разрядах до 11-ти бит и далее кодируется обычным образом. Возвращает кодер 16 бит (кодовое слово).

Код кодера Хэмминга (15, 11) на VB.NET (разворачивается)

Данный кодер легко переписать таким образом, чтобы он работал не с битовыми массивами типа BitArray(), а с байтами: на вход получал 11-разрядное число (от 0 до 0x7FF) и выдавал 2 закодированных байта:

3 Декодер кода Хэмминга (15, 11), написанный на VB.NET

Теперь пора поговорить о декодере. Декодер получает на вход 2 байта закодированных данных и возвращает 11 бит декодированных данных, которые распределены по двум байтам. Если в кодер были переданы 8 бит данных, то нас будет интересовать только первый байт, полученный с декодера.

Код декодера Хэмминга (15, 11) на VB.NET (разворачивается)

4 Консольная программа, кодирующая и декодирующая код Хемминга (15, 11)

Для быстрой проверки кодировщика и декодировщика кода Хэмминга (15, 11), используя вышеописанные классы, я написал две программы. Первая – кодер Хэмминга . Вводите 11-разрядное число (от 0 до 0x7FF или 2047), и на выходе получаем 16-разрядное число, представленное в виде двух байтов.

Внешний вид программы кодера кода Хэмминга (15, 11)

Вторая программа – декодер кода Хмминга (15, 11) .

Внешний вид программы декодера кода Хэмминга (15, 11)

Легко убедиться, что если мы внесём битовую ошибку при декодировании, то декодер восстановит исходное закодированное число.

Обе программы работают под ОС Windows и требуют .NET версии 3.5 . Выкладываю описанные программы.

Способы декодирования — Decoding methods

В теории кодирования , декодирование , представляет собой процесс преобразования принятых сообщений в кодовые слова данного кода . Там было много общих методов отображения сообщений кодовых слов. Они часто используются для восстановления сообщения , отправленные через канал с шумом , например в качестве двоичного симметричного канала .

содержание

нотация

Идеальный декодирования наблюдатель

Можно дать сообщение , то идеальным декодирование наблюдателя генерирует кодовое слово . В результате этого процесса в этом растворе: Икс ∈ F 2 N <\ Displaystyle х \ в \ mathbb _ <2>^ <п>> Y ∈ С

Например, человек может выбрать кодовое слово , которое , скорее всего , будет получено в качестве сообщения после передачи. Y <\ Displaystyle у>Икс

конвенции декодирование

Каждое кодовое слово не имеет ожидаемую возможность: может быть больше, чем одно кодовое слово с равной вероятностью мутировать в принятом сообщении. В таком случае, отправитель и получатель (и) должен согласовать заранее на конвенции декодирования. Популярные конвенции включают:

  1. Запрос о том , что кодовое слово будет возмущаться — автоматический повтор запроса .
  2. Выберите любое случайное кодовое слово из набора наиболее вероятных кодовых слов, который ближе к этому.
  3. Если другой код следует , отметить неоднозначные биты кодового слова как подчистки и надеется , что внешний код устраняет неоднозначность их.

Декодирование по критерию максимального правдоподобия

Учитывая принятое кодовое слово максимального правдоподобия декодирования выбирает кодовое слово , что максимизирует Икс ∈ F 2 N <\ Displaystyle х \ в \ mathbb _ <2>^ <п>> Y ∈ С

то есть кодовое слово , которое максимизирует вероятность того, что было получено, при условии , что было отправлено. Если все кодовые слова в равной степени вероятно, будут отправлены , то эта схема эквивалентна идеальной расшифровке наблюдателя. В самом деле, по байесовской теореме , Y <\ Displaystyle у>Икс <\ Displaystyle х>Y

Как идеальным декодирование наблюдателя, соглашение должно быть согласовано для неоднозначного декодирования.

Максимальная проблема декодирования вероятность того, также может быть смоделирована как целое программирования задачи.

Максимальное правдоподобие декодирования алгоритма является экземпляром «маргинализировать функции продукта» задача , которая решается путем применения обобщенного дистрибутивный закона .

Минимальное расстояние декодирования

Учитывая принятое кодовое слово , минимальное расстояние декодирования выбирает кодовое слово , чтобы минимизировать расстояние Хемминга : Икс ∈ F 2 N <\ Displaystyle х \ в \ mathbb _ <2>^ <п>> Y ∈ С

т.е. выбрать кодовое слово , которое как можно ближе к . Y <\ Displaystyle у>Икс

Обратите внимание , что , если вероятность ошибки на дискретный канал без памяти строго меньше половины, то минимальное расстояние декодирование эквивалентно максимальному декодирования правдоподобия , так как если п

d ( Икс , Y ) знак равно d ,

который (так как р меньше половины) максимизируется путем минимизации д .

Минимальное расстояние декодирование также известно как ближайший сосед декодирование . Она может быть оказана помощь или автоматизирован с использованием стандартного массива . Минимальное расстояние декодирования является разумным способ декодирования , когда выполнены следующие условия:

Эти предположения могут быть разумными для передачи над двоичным симметричным каналом . Они могут быть неразумными для других средств массовой информации, таких как DVD, где одна царапина на диске может привести к ошибке во многих соседних символах или кодовых словах.

Как и с другими методами декодирования, конвенции должны быть согласованы для неоднозначного декодирования.

декодирование синдром

Синдром декодирование является весьма эффективным методом декодирования линейного кода над шумным каналом , то есть тот , на котором сделаны ошибки. В сущности, декодирование синдром является минимальное расстояние декодирования с использованием приведенного таблицы поиска. Это допускается в силу линейности кода.

Предположим , что линейный код длины и минимального расстояния с проверочной матрицей . Тогда , очевидно , способен исправлять до С ⊂ F 2 N <\ Displaystyle С \ подмножество \ mathbb _ <2>^ <п>> N <\ Displaystyle п>d <\ Displaystyle д>ЧАС <\ Displaystyle Н>С

Ошибки , сделанные в канале (так как, если не больше , чем ошибки сделаны , то минимальное расстояние декодирования все равно будет правильно декодировать кодовое слово , переданное неправильно). T

Теперь предположим , что кодовое слово передается по каналу , и вектор ошибки происходит. Затем принимается. Обычное минимальное расстояние декодирование будет LookUp вектора в таблице размера для ближайшего матча — то есть элемент (не обязательно уникального) с Икс ∈ F 2 N <\ Displaystyle х \ в \ mathbb _ <2>^ <п>> е ∈ F 2 N <\ Displaystyle е \ в \ mathbb _ <2>^ <п>> Z знак равно Икс + е <\ Displaystyle г = х + е>Z <\ Displaystyle г>| С | <\ Displaystyle | C |>с ∈ С

d ( с , Z ) ≤ d ( Y , Z )

для всех . Декодирования Syndrome использует свойства матрицы контроля четности , что: Y ∈ С

ЧАС Икс знак равно 0

для всех . Синдром принимаемого определяется как: Икс ∈ С <\ Displaystyle х \ в С>Z знак равно Икс + е

ЧАС Z знак равно ЧАС ( Икс + е ) знак равно ЧАС Икс + ЧАС е знак равно 0 + ЧАС е знак равно ЧАС е

Для того, чтобы выполнить декодирование ML в двоичном симметричном канале , один должно смотреть вверх на предварительно вычисленную таблицу размеров , отображение на . 2 N — К <\ Displaystyle 2 ^ <п>> ЧАС е <\ Displaystyle He>е

Следует отметить , что это уже из значительно менее сложность , чем у стандартного декодирования массива .

Однако, при условии , что не больше , чем не были сделаны во время передачи ошибок, приемник может искать значение в дальнейшем уменьшенной таблице размера T <\ Displaystyle т>ЧАС е

только (для двоичного кода). Таблица с предварительно вычисленными значениями для всех возможных шаблонов ошибок . ЧАС е <\ Displaystyle He>е ∈ F 2 N <\ Displaystyle е \ в \ mathbb _ <2>^ <п>>

Зная , что есть, то тривиальное расшифровать как: е <\ Displaystyle е>Икс

Икс знак равно Z — е

Частичный ответ максимального правдоподобия

Частичный ответ максимального правдоподобия ( PRML ) представляет собой способ для преобразования аналогового сигнала слабого от головки магнитного диска или накопителя на магнитной ленте в цифровой сигнал.

декодер Витерби

Декодер Витерби использует алгоритм Витерби для декодирования битового потока , который был закодирован , используя прямой коррекцию ошибок на основе сверточного кода. Расстояние Хэмминга используется в качестве метрики для жесткого решения Витерби декодеров. Квадрат евклидова расстояния используется в качестве метрики для мягкого решения декодеров.

Как получить имя класса драйвера (не имя драйвера) из соединения jdbc

У меня есть файл context.xml в формате ниже

Из этого contex.xml мне нужно получить имя моего драйвера.

Каждый раз, когда я пытаюсь

DataSource ds = (DataSource)context.lookup(«java:/jdbc/myDataSource»)

и попробуйте получить имя класса драйвера из соединения, используя

Он возвращается только Драйвер Oracle JDBC вместо имени класса oracle.jdbc.driver.OracleDriver

Как получить имя класса из контекста.

Я думаю, что лучшее, на что вы можете надеяться, это:

Метаданные должны вернуть URL для этого соединения, а префикс URL должен быть зарегистрирован с помощью DriverManager (уникально).

Для любого объекта вы можете использовать object.getClass().getName()

Для подключения JDBC это выглядит так:

Для моего драйвера PostgreSQL он возвращает:

В вашем коде это должно работать:

И простая процедура, которая показывает имя класса соединения:

Для соединения Oracle, которое я использовал в тесте, которое я получил:

Синдромное декодирование линейных блочных кодов

Читайте также:

  1. I.1. Общая характеристика нелинейных систем
  2. I.2.Примеры нелинейных систем управления
  3. АВТОМАТИЗИРОВАННОЙ ИДЕНТИФИКАЦИИ ШТРИХОВЫХ КОДОВ
  4. Вес и расстояние Хемминга. Способность кодов обнаруживать и исправлять ошибки
  5. Виды систем линейных уравнений
  6. Геодезические работы при проектировании изысканий сооружений линейного типа (нивелирование трасс линейных сооружений)
  7. Графические методы расчета нелинейных цепей постоянного тока
  8. Декодирование информации циклическими кодами
  9. Декодирование методом максимального правдоподобия
  10. Декодирование сверточных кодов. Алгоритм Витерби
  11. Декодирование сообщений
  12. Измерение линейных и угловых ускорений

Покажем, как можно использовать синдром принятого вектора не только для обнаружения, но и для исправления ошибок.

Пусть U = ( U , U1 , …, Un-1 ), e = ( е , е1, …, еn-1 ) и r = ( r , r1, r2 , …, rn-1) являются передаваемым кодовым словом, вектором-ошибкой и принятым вектором соответственно. Тогда

r = U + e (3.25)

S = r×H T = (U + e )× H T = U× H T + e× H T = 0 + e× H T = e× H T , (3.26)

поскольку для любого кодового слова U × H T = 0.

Таким образом, синдром принятой последовательности r зависит только от ошибки, имеющей место в этой последовательности, и совершенно не зависит от переданного кодового слова. Задача декодера, используя эту зависимость, определить элементы (координаты) вектора ошибок. Найдя вектор ошибки можно восстановить кодовое слово как

U* = r + e . (3.27)

На примере одиночных ошибок при кодировании с использованием линейного блочного (7,4)-кода покажем, как вектор ошибки связан с синдромом, и как, имея синдром, локализовать и устранить ошибки, возникшие при передаче.

Найдем значения синдрома для всех возможных одиночных ошибок в последовательности из семи символов:

e_ = ( 0000000 ),

T
e_ × H T = ( 0000000 ) × = (000);

e = ( 1000000 ),

T
e× H T = ( 1000000 ) × = (110);

e1 = ( 0100000 ),

T
e1× H T = ( 0100000 ) × = (011);

e2 = ( 0010000 ),

T
e2× H T = ( 0010000 ) × = (111);

e3 = ( 0001000 ),

T
e3× H T = ( 0001000 ) × = (101);

e4 = ( 0000100 ),

T
e4× H T = ( 0000100 ) × = (100);

e5 = ( 0000010 ),

T
e5× H T = ( 0000010 ) × = (010);

e6 = ( 0000001 ),

T
e6× H T = ( 0000001 ) × = (001).

Все возможные для (7,4)-кода одиночные ошибки и соответствующие им векторы синдрома приведены в табл. 3.3.

Вектор ошибки Синдром ошибки Десятичный код синдрома

Из этой таблицы видно, что существует однозначное соответствие между сочетанием ошибок (при одиночной ошибке) и его синдромом, то есть, зная синдром, можно совершенно однозначно определить позицию кода, в которой произошла ошибка.

Например, если синдром, вычисленный по принятому вектору, равен ( 111 ), это значит, что произошла одиночная ошибка в третьем символе, если S = ( 001 ) – то в последнем, и т.д.

Если место ошибки определено, то устранить ее уже не представляет никакого труда.

Полная декодирующая схема для (7,4)-кода Хемминга, использующая синдром вектора r не только для обнаружения, но и для исправления ошибок, приведена на рис. 3.6.

А теперь посмотрим, что произойдет, если в принятой последовательности будет не одна, а, например, две ошибки. Пусть ошибки возникли во второй и шестой позициях e = ( 0100010 ). Соответствующий синдром определится как

S = ( 0100010 ) = (001).

Однако синдром S = ( 001 ) соответствует также и одиночной ошибке в седьмой позиции ( e6 ). Следовательно, наш декодер не только не исправит ошибок в позициях, в которых они произошли, но и внесет ошибку в ту позицию, где ее не было. Таким образом, видно, что (7,4)-код не обеспечивает исправления двойных ошибок, а также ошибок большей кратности.

Это, однако, обусловлено не тем, каким образом производится декодирование, а свойствами самого кода. Несколько позднее будет показано, от чего зависит исправляющая способность кода, то есть сколько ошибок он может исправить.

Дата добавления: 2014-01-07 ; Просмотров: 1620 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Помехоустойчивые коды в кодировании сигнала

Принципы помехоустойчивого кодирования

Помехоустойчивым (корректирующим) кодированием называется кодирование при котором осуществляется обнаружение либо обнаружение и исправление ошибок в принятых кодовых комбинациях.

Возможность помехоустойчивого кодирования осуществляется на основании теоремы, сформулированной Шенноном, согласно ей:

если производительность источника (Hи’(A)) меньше пропускной способности канала связи (Ск), то существует по крайней мере одна процедура кодирования и декодирования при которой вероятность ошибочного декодирования сколь угодно мала, если же производительность источника больше пропускной способности канала, то такой процедуры не существует.

Основным принципом помехоустойчивого кодирования является использование избыточных кодов, причем если для кодирования сообщения используется простой код, то в него специально вводят избыточность. Необходимость избыточности объясняется тем, что в простых кодах все кодовые комбинации являются разрешенными, поэтому при ошибке в любом из разрядов приведет к появлению другой разрешенной комбинации, и обнаружить ошибку будет не возможно. В избыточных кодах для передачи сообщений используется лишь часть кодовых комбинаций (разрешенные комбинации). Прием запрещенной кодовой комбинации означает ошибку. Причем, в процессе приема закодированного сообщения возможны три случая (рисунок 3).

Рисунок 3 — Случаи приема закодированного сообщения

Прием сообщения без ошибок является оптимальным, но возможен только если канал связи идеальный. В этом случае помехоустойчивое декодирование не нужно.

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

Если же передаваемая разрешенная кодовая комбинация, в результате воздействия помех, трансформируется в запрещенную комбинация, то в этом случае существует возможность обнаружить ошибку и исправить ее.

Помехоустойчивое кодирование может осуществляться двумя способами: с обнаружением ошибок либо с исправлением ошибок. Возможность кода обнаруживать или исправлять ошибки определяется кодовым расстоянием.

Если осуществляется кодирование с обнаружением ошибок, то кодовое расстояние должно быть хотя бы на единицу больше чем кратность обнаруживаемых ошибок, т. е.

Если данное условие не выполняется, то одни из ошибок обнаруживаются, а другие нет.

Если осуществляется кодирование с исправлением ошибок, то кодовое расстояние должно быть хотя бы на единицу больше удвоенного значения кратности исправляемых ошибок, т. е.

Если данное условие не выполняется, то одни из ошибок исправляются, а другие нет.

Следует отметить, что если код способен исправить одну ошибку (qи ош = 1), что соответствует кодовому расстоянию 3 (d = 1?2+1 = 3), то обнаружить он может две ошибки, т. к.

Декодирование помехоустойчивых кодов

Декодирование это процесс перехода от вторичного отображения сообщения к первичному алфавиту.

Декодирование помехоустойчивых кодов может осуществляться тремя способами: сравнения, синдромным и мажоритарным.

Способ сравнения основан на том, что, принятая кодовая комбинация сравнивается со всеми разрешенными комбинациями, которые заранее известны на приеме. Если принятая комбинация не совпадает ни с одной из разрешенных, выносится решение о принятии запрещенной комбинации. Недостатком данного способа является громоздкость и необходимость большого времени для декодирования в случае применения многоразрядных кодов. Данный способ используется в кодах с обнаружением ошибок.

Синдромный способ основан на вычислении определенным образом контрольного числа — синдрома ошибки (С). Если синдром ошибки равен нулю, то кодовая комбинация принята верно, если синдром не равен нулю, то комбинация принята не верно. Данный способ может быть использован в кодах с исправлением ошибок, в этом случае синдром указывает не только на наличие ошибки в кодовой комбинации, но и на место положение этой ошибки в кодовой комбинации. Для двоичного кода знание местоположения ошибки достаточно для ее исправления. Это объясняется тем, что любой символ кодовой комбинации может принимать всего два значения и если символ ошибочный, то его необходимо инвертировать. Следовательно, синдрома ошибки достаточно для исправления ошибок, если d? 2qи ош + 1.

Мажоритарное декодирование основано на том, что каждый информационный символ кодовой комбинации определяется нескольким линейными выражениями через другие символы кодовой комбинации. Если принята комбинация без ошибок, то все соотношения остаются и все выражения дают одинаковые результаты (единицу или ноль). При ошибке в одном из разрядов эти соотношения нарушаются, в результате чего одни линейные выражения равны нулю, а другие единице. Решение о принятом символе определяется по большинству: если в результате вычислений выражений больше нулей, то принимается решение о принятии нуля, если больше единиц, то принимается решение о приеме единицы. Если, при декодировании, результаты вычисления выражений дают одинаковое число единиц и нулей, то при определении принятого символа приоритет имеет принятый символ, значение которого в данный момент определяется.

Классификация корректирующих кодов

Классификация корректирующих кодов представлена схемой (рисунок 4)

Блочные — это коды, в которых передаваемое сообщение разбивается на блоки и каждому блоку соответствует своя кодовая комбинация (например, в телеграфии каждой букве соответствует своя кодовая комбинация).

Рисунок 4 — Классификация корректирующих кодов

Непрерывные — коды, в которых сообщение не разбивается на блоки, а проверочные символы располагаются между информационными.

Неразделимые — это коды, в кодовых комбинациях которых нельзя выделить проверочные разряды.

Разделимые — это коды, в кодовых комбинациях которых можно указать положение проверочных разрядов, т. е. кодовые комбинации можно разделить на информационную и проверочную части.

Систематические (линейные) — это коды, в которых проверочные символы определяются как линейные комбинации информационных символов, в таких кодах суммирование по модулю два двух разрешенных кодовых комбинаций также дает разрешенную комбинацию. В несистематических кодах эти условия не выполняются.

Код с постоянным весом

Данный код относится к классу блочных не разделимых кодов. В нем все разрешенные кодовые комбинации имеют одинаковый вес. Примером кода с постоянным весом является Международный телеграфный код МТК-3. В этом коде все разрешенные кодовые комбинации имеют вес равный трем, разрядность же комбинаций n=7. Таким образом, из 128 комбинаций (N = 2 7 = 128) разрешенными являются Nа = 35 (именно столько комбинаций из всех имеют W=3). При декодировании кодовых комбинаций осуществляется вычисление веса кодовой комбинации и если W?3, то выносится решение об ошибке. Например, из принятых комбинаций 0110010, 1010010, 1000111 ошибочной является третья, т. к. W=4. Данный код способен обнаруживать все ошибки нечетной кратности и часть ошибок четной кратности. Не обнаруживаются только ошибки смещения, при которых вес комбинации не изменяется, например, передавалась комбинация 1001001, а принята 1010001 (вес комбинации не изменился W=3). Код МТК-3 способен только обнаруживать ошибки и не способен их исправлять. При обнаружении ошибки кодовая комбинация не используется для дальнейшей обработки, а на передающую сторону отправляется запрос о повторной передаче данной комбинации. Поэтому данный код используется в системах передачи информации с обратной связью.

Код с четным числом единиц

Данный код относится к классу блочных, разделимых, систематических кодов. В нем все разрешенные кодовые комбинации имеют четное число единиц. Это достигается введением в кодовую комбинацию одного проверочного символа, который равен единице если количество единиц в информационной комбинации нечетное и нулю ? если четное. Например:

При декодировании осуществляется поразрядное суммирование по модулю два всех элементов принятой кодовой комбинации и если результат равен единице, то принята комбинация с ошибкой, если результат равен нулю принята разрешенная комбинация. Например:

101101 = 1 + 0 + 1 + 1 + 0 + 1 = 0 — разрешенная комбинация

101111 = 1 + 0 + 1 + 1 + 1 + 1 = 1 — запрещенная комбинация.

Данный код способен обнаруживать как однократные ошибки, так и любые ошибки нечетной кратности, но не способен их исправлять. Данный код также используется в системах передачи информации с обратной связью.

Код Хэмминга

Код Хэмминга относится к классу блочных, разделимых, систематических кодов. Кодовое расстояние данного кода d=3 или d=4.

Блочные систематические коды характеризуются разрядностью кодовой комбинации n и количеством информационных разрядов в этой комбинации k остальные разряды являются проверочными (r):

Данные коды обозначаются как (n,k).

Рассмотрим код Хэмминга (7,4). В данном коде каждая комбинация имеет 7 разрядов, из которых 4 являются информационными,

При кодировании формируется кодовая комбинация вида:

где аi — информационные символы;

bi — проверочные символы.

В данном коде проверочные элементы bi находятся через линейные комбинации информационных символов ai, причем, для каждого проверочного символа определяется свое правило. Для определения правил запишем таблицу синдромов кода (С) (таблица 3), в которой записываются все возможные синдромы, причем, синдромы имеющие в своем составе одну единицу соответствуют ошибкам в проверочных символах:

  • синдром 100 соответствует ошибке в проверочном символе b1;
  • синдром 010 соответствует ошибке в проверочном символе b2;
  • синдром 001 соответствует ошибке в проверочном символе b3.

Синдромы с числом единиц больше 2 соответствуют ошибкам в информационных символах. Синдромы для различных элементов кодовой комбинации аi и bi должны быть различными.

Таблица 3 — Синдромы кода Хэмминга (7;4)

Число Элементы синдрома Элементы кодовой
синдрома С1 С2 С3 комбинации
1 1 b3
2 1 b2
3 1 1 a1
4 1 b1
5 1 1 a2
6 1 1 a3
7 1 1 1 a4

Определим правило формирования элемента b3. Как следует из таблицы, ошибке в данном символе соответствует единица в младшем разряде синдрома С4. Поэтому, из таблицы, необходимо отобрать те элементы аi у которых, при возникновении ошибки, появляется единица в младшем разряде. Наличие единиц в младшем разряде, кроме b3,соответствует элементам a1, a2 и a4. Просуммировав эти информационные элементы получим правило формирования проверочного символа:

Аналогично определяем правила для b2 и b1:

Пример 3, необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем bi:

b1 = 1 + 0 + 1 = 0; b2 = 1 + 0 + 1=1; b3 = 1 + 1 + 1 = 1.

Добавляем проверочные символы к информационным и получаем кодовую комбинацию:

В теории циклических кодов все преобразования кодовых комбинаций производятся в виде математических операций над полиномами (степенными функциями). Поэтому двоичные комбинации преобразуют в полиномы согласно выражения:

где an-1, … коэффициенты полинома принимающие значения 0 или 1. Например, комбинации 1001011 соответствует полином

Аi(х) = 1?x 6 + 0?x 5 + 0?x 4 + 1?x 3 + 0?x 2 + 1?x+1?x 0 ? x 6 + x 3 + x+1.

При формировании кодовых комбинаций над полиномами производят операции сложения, вычитания, умножения и деления. Операции умножения и деления производят по арифметическим правилам, сложение заменяется суммированием по модулю два, а вычитание заменяется суммированием.

Разрешенные кодовые комбинации циклических кодов обладают тем свойством, что все они делятся без остатка на образующий или порождающий полином G(х). Порождающий полином вычисляется с применением ЭВМ. В приложении приведена таблица синдромов.

Этапы формирования разрешенной кодовой комбинации разделимого циклического кода Biр(х).

1. Информационная кодовая комбинация Ai преобразуется из двоичной формы в полиномиальную (Ai(x)).

2. Полином Ai(x) умножается на х r ,

где r количество проверочных разрядов:

3. Вычисляется остаток от деления R(x) полученного произведения на порождающий полином:

4. Остаток от деления (проверочные разряды) прибавляется к информационным разрядам:

5. Кодовая комбинация Bip(x) преобразуется из полиномиальной формы в двоичную (Bip).

Пример 4. Необходимо сформировать кодовую комбинацию циклического кода (7,4) с порождающим полиномом G(x)=х 3 +х+1, соответствующую информационной комбинации 0110.

1. Преобразуем комбинацию в полиномиальную форму:

Ai = 0110 ? х 2 + х = Ai(x).

2. Находим количество проверочных символов и умножаем полученный полином на x r :

r = n – k = 7 – 4 =3

Ai(x)?x r = (х 2 + х)? x 3 = х 5 + х 4

3. Определяем остаток от деления Ai(x)?x r на порождающий полином, деление осуществляется до тех пор пока наивысшая степень делимого не станет меньше наивысшей степени делителя:

R(x) = Ai(x)?x r /G(x)

4. Прибавляем остаток от деления к информационным разрядам и переводим в двоичную систему счисления:

Biр(x) = Ai(x)?x r + R(x) = х 5 + х 4 + 1? 0110001.

5. Преобразуем кодовую комбинацию из полиномиальной формы в двоичную:

Biр(x) = х 5 + х 4 + 1 ? 0110001 = Biр

Как видно из комбинации четыре старших разряда соответствуют информационной комбинации, а три младших — проверочные.

Формирование разрешенной кодовой комбинации неразделимого циклического кода.

Формирование данных комбинаций осуществляется умножением информационной комбинации на порождающий полином:

Причем умножение можно производить в двоичной форме.

Пример 5, необходимо сформировать кодовую комбинацию неразделимого циклического кода используя данные примера 2, т. е. G(x) = х 3 +х+1, Ai(x) = 0110, код (7,4).

1. Переводим комбинацию из двоичной формы в полиномиальную:

Ai = 0110? х 2 +х = Ai(x)

3. Переводим кодовую комбинацию из полиномиальной форы в двоичную:

Bip(x) = х 5 +х 4 +х 3 +х ? 0111010 = Bip

В этой комбинации невозможно выделить информационную и проверочную части.

Матричное представление систематических кодов

Систематические коды, рассмотренные выше (код Хэмминга и разделимый циклический код) удобно представить в виде матриц. Рассмотрим, как это осуществляется.

Поскольку систематические коды обладают тем свойством, что сумма двух разрешенных комбинаций по модулю два дают также разрешенную комбинацию, то для формирования комбинаций таких кодов используют производящую матрицу Gn,k. С помощью производящей матрицы можно получить любую кодовую комбинацию кода путем суммирования по модулю два строк матрицы в различных комбинациях. Для получения данной матрицы в нее заносятся исходные комбинации, которые полностью определяют систематический код. Исходные комбинации определяются исходя из условий:

1) все исходные комбинации должны быть различны;

2) нулевая комбинация не должна входить в число исходных комбинаций;

3) каждая исходная комбинация должна иметь вес не менее кодового расстояния, т. е. W?d;

4) между любыми двумя исходными комбинациями расстояние Хэмминга должно быть не меньше кодового расстояния, т. е. dij?d.

Производящая матрица имеет вид:

Производящая подматрица имеет k строк и n столбцов. Она образована двумя подматрицами: информационной (включает элементы аij) и проверочной (включает элементы bij). Информационная матрица имеет размеры k?k, а проверочная — r?k.

В качестве информационной подматрицы удобно брать единичную матрицу Ekk:

Проверочная подматрица Gr,k строится путем подбора различных r-разрядных комбинаций, удовлетворяющих следующим правилам:

1) в каждой строке подматрицы количество единиц должно быть не менее d-1;

2) сумма по модулю два двух любых строк должна иметь не менее d-2 единицы;

Полученная таким образом подматрица Gr,k приписывается справа к подматрице Ekk, в результате чего получается производящая матрица Gn,k. Затем, используя производящую матрицу, можно получить любую комбинацию кода путем суммирования двух и более строк по модулю два в различных комбинациях.

Пример 6. Необходимо построить производящую матрицу кода Хэмминга способного исправлять 1 ошибку и имеющего n=7. Закодировать с помощью полученной матрицы комбинацию Ai=1101.

Определяем кодовое расстояние:

Для кодов с d=3 количество проверочных разрядов определяется по формуле:

Определяем разрядность информационной части:

Запишем все возможные комбинации проверочной подматрицы: 000, 001, 010, 011, 100, 101, 110, 111. Выберем из этих комбинаций те, что удовлетворяют правилам:

1) в каждой строке не менее d-1, этому условию соответствуют комбинации 011, 101, 110, 111;

2) сумма двух любых комбинаций по модулю два содержит единиц не менее d-2:

3) записываем проверочную подматрицу:

4) приписываем полученную подматрицу к единичной и получаем производящую матрицу:

Если произвести определение d для исходных комбинаций полученной матрицы (определив расстояние Хэмминга для всех пар комбинаций), то оно окажется равным 3.

Для кодирования заданной комбинации Ai, необходимо просуммировать те строки матрицы G, которые в информационной части имеют единицу на том месте, на котором они находятся в комбинации Аi. Для заданной комбинации 1101 единичными разрядами являются а1, а2, а4. В матрице G единицы на этих местах имеют строки: первая, вторая и четвертая. Просуммировав их получаем разрешенную комбинацию заданного кода.

Сравнивая полученную кодовую комбинацию Bip с комбинацией полученной примере 3, для которой также использована комбинация Ai=1101, видим что они одинаковы.

Для кода Хэмминга выше были определены правила формирования проверочных символов bk:

Эти правила можно отобразить в виде проверочной матрицы Нn,k. Она состоит из n столбцов (соответствует разрядности кодовой комбинации) и r столбцов (соответствует количеству проверочных разрядов кодовой комбинации). В правой части матрицы указываются синдромы, соответствующие ошибкам в проверочных символах, в левой части записываются элементы информационной части комбинации, причем, те элементы, которые участвуют в образовании определенного элемента bi равны единицы, а те которые не участвуют — нулю.

В данном случае обведенные пунктиром проверочные элементы образуют единичную матрицу. Проверочная матрица позволяет определить ошибочный разряд, поскольку каждый столбец данной матрицы представляет собой синдром соответствующего символа. При этом строки матрицы будут соответствовать разрядам синдрома Ck. Например, согласно приведенной проверочной матрице, синдром соответствующий ошибку в разряде а1 имеет вид 011, в разряде а2 — 101, в разряде а3 — 110, в разряде а4 — 111, в разряде b1 — 100, в разряде b2 — 010, в разряде b3 — 001. Также с помощью проверочной матрицы легко определить проверочные и символы и сформировать кодовую комбинацию. Например, необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем bi:

b1 = 1 + 0 + 1 = 0; b2 = 1 + 0 + 1=0; b3 = 1 + 1 + 1 = 1.

Добавляем проверочные символы к информационным и получаем кодовую комбинацию:

Также проверочную матрицу можно построить и другим способом. Для этого сначала строится единичная матрица Еr. К которой слева приписывается подматрица Dk,r. Каждая строка этой подматрицы соответствует столбцу проверочных разрядов подматрицы Сr,k производящей матрицы Gn,k.

Такое преобразование строк матрицы в столбцы называется транспонированием.

В результате получаем

Декодирование циклических кодов

При декодировании таких кодов (разделимых и неразделимых) используется Синдромный способ. Вычисление синдрома осуществляется в три этапа:

1. принятая комбинация Bip’ преобразуется их двоичной формы в полиномиальную (Bip(x));

2. осуществляется деление Bip(x) на порождающий полином G(x) в результате чего определяется синдром ошибки C(x) (остаток от деления);

3. синдром ошибки преобразуется из полиномиальной формы в двоичную;

4. По проверочной матрице или таблице синдромов определяется ошибочный разряд;

5. Ошибочный разряд в Bip’(x) инвертируется;

6. Исправленная комбинация преобразуется из полиномиальной формы в двоичную Bip.

делением принятой кодовой комбинации Biр’(x) на порождающий полином G(x), который заранее известен на приеме. Остаток от деления и является синдромом ошибки С(х).

Мажоритарное декодирование циклических кодов

Мажоритарное декодирование может применятся только для декодирования систематических кодов (кода Хэмминга, циклического разделимого кода). Рассмотрим мажоритарное декодирование на примере циклического кода.

QR-коды — что это такое, как создать и расшифровать любой баркод, онлайн генераторы и программы для их считывания

Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. При написании прошлой статьи про Liqpay обнаружил на их главной странице, еще не ставший привычным, хитрый код для смартфонов. Сам недавно познакомился с этой темой и поэтому сегодня хочу поговорить о такой вещи, как QR-коды.

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

Начнем с того, что популярность такого типа кодирования информации объясняется прежде всего развитием технологий и практически повсеместным распространением телефонов с хорошей фотокамерой и приличной производительностью. Чтобы расшифровать QR-код достаточно иметь обычный мобильник и установленную на него программу декодирования.

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

Предназначение QR-кодов и их использование

QR-коды — это прежде всего удобство. Но давайте посмотрим, как можно самим их создавать в онлайн генераторах, а так же считывать и расшифровывать на ваших сотовых телефонах. Ну, и в силу принадлежности этого блога к тематике вебмастеринга рассмотрим плагины для WordPress, которые позволят отображать на каждой странице сайта barcode с ее URL адресом, например, для добавления ее в закладки смартфона.

Выглядит эта вариация баркода примерно так:

Представляет он из себя изображение, на котором, как правило, всегда можно выделить три больших квадрата. Они служат ориентирами при расшифровки кода программами для его считывания — помогают определить уровень наклона и четко привязаться к масштабу. Раньше повсеместно использовался более простой одномерный (линейный) barcode (штрих-код):

С помощью штрих-кода можно зашифровать всего лишь от 20 до 30 символов и этого вполне хватало, например, для нужд складской логистики. QR же является одной из разновидностей двухмерного баркода и позволяет существенно увеличить объем заключенной в нем информации. В идеале с его помощью можно перевести в относительно небольшое изображение до двух с половиной печатных страниц текста.

В реальности же кодируют от нескольких десятков до сотен символов, ибо большее количество может вызвать сложности в расшифровке мобильными телефонами в неидеальных условиях. К тому же до 30 процентов информации может быть отдано на избыточность, которая позволит расшифровать QR-код даже при его частичном повреждении или в плохих условиях.

Подсадили весь мир на эту «заразу» японцы. Одна из их компаний разработала принципы кодирования и расшифровывания в середине девяностых годов прошлого века. Ну, а повсеместное распространение сотовых в стране восходящего солнца обеспечило большинство населения персональными сканерами баркода.

Помимо товаров, рекламных плакатов, визиток, уличных указателей и всего остального, в Японии даже информация о покойниках на кладбищах кодируется с помощью него. Более подробно можете прочитать в этой публикации.

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

Если вы, например, захотели добавить интересную статью в закладки сотового (для его прочтения в дороге), то для всех современных браузеров предусмотрены дополнения и плагины, позволяющие закодировать URL адреса в QR, а затем вы сможете его считать камерой мобильного телефона и указанная страница будет открыта в мобильном браузере. Тоже самое касается выделенных фрагментов текста.

Я уже как-то писал про плагины для Firefox и упоминал там про расширение под названием Mobile Barcoder, которое позволяет создавать их для любой ссылки или выделенного фрагмента текста (пункт меню Create barcode):

Если захотите передать с помощью QR-кода в свой сотовый фрагмент текста, то результирующая картинка получится существенно более информационно-наполненной и вашему мобильнику, скорее всего, придется чуток потрудиться чтобы ее расшифровать:

Если Мазила не является вашим любимым браузером, то можете воспользоваться расширением для Гугол Хрома — Goo.gl URL Shortener (правда, он предназначен в первую очередь для укорачивания ссылок, но и баркоды из ссылок он тоже умеет делать). В Опере можно использовать в качестве генератора QR Code Generator.

Как создать QR-код — онлайн генераторы

Чуть выше мы рассмотрели генераторы интегрированные в браузеры, но гораздо более функциональными выглядят их онлайн версии, которые могут закодировать нужную вам информацию (URL адрес, текст, личные данные с визитной карточки, SMS, номер телефона и т.п.) и создать картинку нужного вам размера. Результирующее изображение barcode вы сможете сохранить на своем компьютере или получить на него ссылку.

QR Hacker — служит для создания эксклюзивных изображений с баркодами, которые вы сможете раскрасить, скруглить им углы и даже добавить свой логотип. Т.к. в этой технологии изначально заложена избыточность кода (до 30%), то данные издевательства не приведут к потере информации.

Сначала в левой панели генератора выбираете тип данных — это нужно, чтобы программа расшифровщик в вашем мобильнике знала, чего с этими данными делать в дальнейшем — открывать ссылку в браузере, показывать текст, добавлять данные в контакты или еще чего-то делать. На следующем шаге в расположенной чуть ниже форме вводите то, что вы хотите закодировать (в моем случае это URL — https://ktonanovenkogo.ru) и жмете на кнопку «Generate».

В окне редактора появится обычный черно-белый QR-код, который можно будет либо сохранить в таком виде, либо разукрасить. Все инструменты редактора находятся в правой панели. Если рассматривать их сверху вниз, то сначала идет движок скругления углов у элементов, потом инструменты для задания фона цветом, либо загрузки и настройки прозрачности фонового изображения.

Ну, а чуть ниже расположены инструменты для раскраски самих элементов (прям как детские раскраски Пет Шоп) и размещения логотипа на поверхности создаваемого баркода. Под изображением, над которым вы издеваетесь, расположена цветовая шкала, которая косвенно характеризует его читаемость. На приведенном чуть выше скриншоте читаемость находится на грани, хотя мой телефон с установленной программой расшифровки I-nigma (созвучно, с поисковой системой Nigma, не правда ли) справился с этой задачей на ура.

QR Coder.ru — простенький генератор barcode с интерфейсом на русском языке. Сначала следует выбрать тот тип информации, который вы хотите зашить в картинку (текст, визитка, SMS или URL) для того, чтобы программа для считывания предложила бы вам нужные варианты дальнейших действий. Например, в случае визитки вам будет предложено заполнить следующие поля:

Для ссылок это будет открытие в браузере, а для данных визитной карточки — сохранение в контактах (либо набрать номер из визитки):

Qrmania.ru — еще один русскоязычный генератор QR-кодов с несколько более расширенным функционалом, который в первую очередь связан с большим разнообразием типов информации, которую можно закодировать и цветовыми настройками итоговой картинки:

Имеет место быть возможность кодирования E-mail адреса и целого почтового сообщения с указанием адресата, темы и текста письма. Кроме этого можно закодировать номер телефона (было бы удобно, если бы девушки носили значки или сумки с таким баркодом), Твиттер сообщения и даже координаты на Google картах. Чума!

Вообще, конечно же, сервис Qrmania можно назвать апофеозом QR генераторов, ибо созданное изображение можно будет не только сохранить на своем компьютере, но и заказать его печать на футболке, бейсболке, значке, сумке и прочей мелочи за вполне вменяемые деньги:

Да, я в начале статьи заикался о плагинах для WordPress, которые бы позволяли генерировать на лету QR для страниц вашего блога. Почти уже забыл об этом, но все же приведу ссылку на страницу автора этих плагинов. Сам я еще не осознал необходимости прикручивания barcode для всех страниц блога, но, возможно, со временем передумаю.

Ну, и напоследок не премину привести ссылку на статью, где можно будет посмотреть несколько десятков высокохудожественных баркодов. Примечательно, но все проверенные мною картинки из этой статьи уверенно расшифровываются мобильником.

Как расшифровать баркод — программы и онлайн сервисы

Другой вопрос — чем можно расшифровать такие замысловатые картинки на мобильном телефоне. Набор подобных программ довольно велик и многое будет зависеть от типа вашего телефона, а точнее от той ОС, на базе которой он работает (Андроид, Ios и т.п.).

Лично я юзаю телефон Нокиа E72 и больше всего мне понравилась I-nigma — просто переходите с сотового по этой ссылке, сайт разработчиков автоматически сам определит тип вашего аппарата и предложит закачать программу для считывания и расшифровки QR-кодов. Поддерживается, по-моему, все, что только можно придумать (в плане моделей телефонов). Скриншот работы I-nigma вы сможете найти чуть выше по тексту.

Однако, прежде, чем рассматривать дальше программы сканирования для мобильных телефонов, я хочу остановиться на онлайн сервисах, помогающих расшифровать любой баркод. Зачем это может понадобиться с ходу и не придумаешь, но если таковые сервисы имеют место быть, то и потребность в них есть тоже.

Работает он очень просто. Вам предлагают указать URL изображения с QR кодом, которое расположено в интернете или же загрузить его со своего компьютера. После того, как вы нажмете кнопку «Отправить», откроется страница с результатами расшифровки. Все очень просто.

  • Тоже самое может делать и онлайн генератор Qr.foxtools.ru. Выбираете вариант расшифровки и опять же получаете два варианта загрузки картинки с barcode:
  • Думаю, что большего количества онлайн сервисов, позволяющих декодировать любой баркод, и не потребуется, ибо это скорее форс мажорные действия, которые ничего общего с удобством мобильного распознавания не имеют.

    Да, еще стоит упомянуть десктопную программу, ибо тоже имеет право на жизнь. Называется она BarCapture.

    Достаточно будет просто обвести область с QR-кодом и после отпускания мыши вы узнаете ответ, что именно было в нем зашифровано. На мой взгляд, эта программа работает хуже, чем ее аналоги на сотовом телефоне, поэтому особо пользоваться ей не рекомендую, разве что только в случае форс мажора и отсутствия мобильника под рукой.

    Ну, и теперь самое время переходить к наиболее популярным программам считывания и расшифровывания баркода для мобильных телефонов:

    1. I-nigma — уже упоминал эту программу, которая существует для разных мобильных платформ
    2. Barcodes Scanner — популярное приложение, которое существует в вариации для Андроида и для Ios.
    3. QuickMark — подойдет практически для любого мобильного устройства
    4. BeeTagg — еще одна универсальная программа для сканирования и распознавания QR-кода, подходящая для огромного числа моделей мобильников
    5. UpCode — опять же мультлатформенный сканер и дешифратор
    6. Neo Reader — ну, вы поняли
    7. Расшифровать QR-код самому — статья на Хабре о том, как обойтись без программ для считывания

    Ну, и хочу попрощаться в нетрадиционной манере:

    Манчестерский код. Синхронизация, приём и декодирование

    Итак, для начала поговорим о том, что представляет собой «манчестерское» кодирование.

    В «манчестерском» коде единица кодируется переходом сигнала в середине битового интервала из состояния «OFF» в состояние «ON», а ноль — наоборот, переходом сигнала в середине
    битового интервала из состояния «ON» в состояние «OFF».

    Что такое состояния «ON» и «OFF»?
    Состояния сигнала «ON» и «OFF» — это логические состояния. В общем случае «OFF» — это неактивное состояние, такое же, как при отсутствии какого-либо обмена вообще, а «ON» — это активное состояние, то есть такое, которое как-либо отличается от неактивного. Поэтому, несмотря на то, что на картинке справа состояние сигнала «ON» показано высоким уровнем сигнала, а состояние «OFF» показано низким уровнем, это не нужно понимать буквально (просто с высоким и низким уровнем картинка привычнее и нагляднее). На самом деле состояния «ON» и «OFF» могут быть закодированы совершенно по-разному. Например, ИК-пульты кодируют эти состояния наличием или отсутствием импульсов на определённой частоте, интегральные фотоприёмники (у которых чаще всего неактивным является высокий уровень сигнала на выходе) выдают код, в котором «ON» закодировано низким уровнем, а «OFF» — высоким и т.д.

    Длительность нуля и единицы в манчестерском кодировании одинаковая, то есть длина сообщения не зависит от того, сколько в сообщении нулей или единиц, а зависит только от общего количества бит.

    Ключевым свойством «манчестерского» кодирования является то, что при передаче каждого бита обязательно присутствуют оба состояния сигнала: «ON» и «OFF» (ещё раз смотрим на рисунок вверху). То есть, во время передачи каждого бита сигнал должен хотя бы раз изменить своё состояние. То есть «манчестерский» код может состоять только из интервалов одинарной, если соседние биты одинаковые, и двойной, если соседние биты отличаются, длительности (это продемонстрировано на рисунке слева).

    Описанное свойство позволяет дополнительно синхронизировать приёмник с передатчиком при приёме каждого бита, определять — может ли вообще принимаемый код быть «манчестерским», диагностировать конец сообщения или «потерю» сигнала передатчика.

    Скажем, если предположить, что частота передатчика не может скачком измениться более чем в 1,5 раза, то отсутствие изменения состояния сигнала в течении 3-х полубит можно смело трактовать как конец сообщения или «потерю» сигнала передатчика (если мы заранее знаем длину сообщения). Или, например, при исследовании какого-то неизвестного кода, если мы видим, что в коде присутствует более двух вариантов интервалов между состояниями «ON» и «OFF», то можно однозначно сделать заключение о том, что исследуемый код не «манчестерский».

    Надеюсь, с тем, что такое «манчестерский» код, всё более или менее понятно, поэтому переходим к следующему вопросу — как этот код принимать и декодировать.

    Ну, очевидно, что определить начало передачи данных можно по изменению состояния сигнала, воспринимаемого приёмником, с «OFF» на «ON». Однако тут есть один нюанс. Поскольку передача единицы тоже начинается с состояния «OFF», то при первом изменении сигнала из «OFF» в «ON» мы совершенно никак не сможем диагностировать что это — середина передачи единицы или начало передачи нуля. Единственное, что тут можно сделать — это заранее условиться, какой бит должен передаваться первым (то есть ввести специальный старт-бит, значение которого будет всегда строго определено).

    Всё, теперь, если мы знаем с какого бита посылка начинается, знаем длительности интервалов состояний «ON» и «OFF», наш приёмник обладает точным, стабильным генератором и мы
    точно знаем сколько хотим принять бит, то можно составить первый простейший алгоритм восстановления исходной, закодированной «манчестерским» кодом посылки:

    1. — по изменению состояния сигнала с «OFF» на «ON» определяем начало передачи
    2. — отсчитываем четверть длительности бита (чтобы попасть в середину полубита)
    3. — начинаем записывать значение сигнала. С этого момента и далее через интервалы, равные длительности бита. И так — до получения необходимого количества бит.

    Вариант второй. Мы знаем с какого бита посылка начинается, знаем длительности интервалов «ON» и «OFF», наш приёмник обладает стабильным генератором, но мы ничего не знаем о длине сообщения. В этом случае можно воспользоваться тем свойством манчестерского кода, что сигнал не может оставаться постоянным в течении 3-х и более полубит. То есть, момент, когда сигнал в течении 3-х полубит остаётся в состоянии «OFF» можно считать концом сообщения. Алгоритм восстановления исходного кода в этом случае может выглядеть так:

    1. — по изменению состояния сигнала с «OFF» на «ON» определяем начало передачи
    2. — отсчитываем четверть длительности бита (чтобы попасть в середину полубита)
    3. — с этого момента (пусть это будет момент номер 1) и далее, через интервалы, равные длительности полубита, анализируем значение сигнала. Как только
      случится такое, что сигнал в трёх последних замерах будет в состоянии «OFF» — это будет сигнализировать об окончании сообщения. Кроме того, записывая значение сигнала во все моменты с нечетными номерами, кроме последнего, — мы восстановим исходное сообщение.

    Вариант третий. Мы знаем с какого бита посылка начинается, но не знаем длительности интервалов, в течении которых сигнал находится в состоянии «ON» и «OFF». Что нам делать в
    этом случае? Если вы по счастливой случайности знаете значение не только первого бита, но и второго, — значит вам точно известно, через какие интервалы (через целый бит или через половину)
    произойдут первые 2 переключения и вы с лёгкостью можете необходимые интервалы засечь или, научно выражаясь, — синхронизировать приёмник с передатчиком.
    (Ага, вот мы и раскусили зачем у RC-5 целых 2 стартовых бита. Кстати, в сетях ethernet, где тоже используется «манчестерское» кодирование, для начальной синхронизации используется целая 56-битная преамбула).
    Далее можно легко воспользоваться первым или вторым из приведённых выше алгоритмов.

    Ну и, предположим, ещё один вариант. Мы знаем первые два бита посылки, но наш генератор — полное говно, хотя и работает (или, говоря научными терминами, мы можем гарантировать, что за время, равное длительности полубита, частота генератора не может измениться в 1,5 раза и более). Тут-то как быть?

    Да просто надо по каждому новому фронту заново вычислять значения длительности полубита и целого бита. То есть, другими словами, нужно синхронизировать приёмник с передатчиком не один раз в самом начале, а по каждому новому фронту (под фронтом будем понимать переключения между состояниями «ON»/»OFF»), благо при манчестерском кодировании у нас новый фронт присутствует в каждом передаваемом бите.

    Короче говоря, рассматривать разные комбинации можно долго, запомните главное преимущество, за которое «манчестерский» код всем так полюбился: при передаче каждого бита существует изменение состояния «ON»/»OFF», которое даёт возможность синхронизировать передатчик и приёмник.

    Кроме описанного выше, существует ещё, так называемое, «разностное» или «дифференциальное» «манчестерское» кодирование. В данном случае при передаче нуля битовый интервал начинается с изменения состояния сигнала на противоположное, а при передаче единицы — состояние сигнала в начале битового интервала не изменяется. В остальном всё так же, как и в обычном «манчестерском» кодировании — в середине битового интервала состояние сигнала обязательно меняется на противоположное (смотрим рисунок слева).

    Самодельные ИК-пульты и приёмники сигналов дистанционного управления

    Илон Маск рекомендует:  Сохранения параметров приложения в net
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL