Gdd6bSg8vk.n4_H/img-Pv2fju.png' alt='Код Бчх Пример' title='Код Бчх Пример' />Помехоустойчивое кодирование с иcпользованием различных кодов Хабрахабр. Это продолженеие статьи о помехоустойчивом кодировании, которая очень долго лежала в черновиках. В прошлой части нет ничего интересного с практической точки зрения лишь общие сведения о том, зачем это нужно, где применяется и т. В данной части будут рассматриваться некоторые самые простые коды для обнаружения иили исправления ошибок. Итак, поехали. Попытался все описать как можно легче для человека, который никогда не занимался кодированием информации, и без каких либо особых математических формул. Инструкция По Охране Труда Кассира Билетной Кассы. Когда мы передаем сообщение от источника к приемнику, при передаче данных может произойти ошибка помехи, неисправность оборудования и пр. Чтобы обнаружить и исправить ошибку, применяют помехоустойчивое кодирование, т. Для кодирования на передающей стороне используются кодер, а на принимающей стороне используют декодер для получения исходного сообщения. Избыточность кода это количество проверочной информации в сообщении. Рассчитывается она по формуле kik, где k количество проверочных бит,i количество информационных бит. Например, мы передаем 3 бита и к ним добавляем 1 проверочный бит избыточность составит 131 14 2. Код с проверкой на четность. Проверка четности очень простой метод для обнаружения ошибок в передаваемом пакете данных. С помощью данного кода мы не можем восстановить данные, но можем обнаружить только лишь одиночную ошибку. Id10.png' alt='Код Бчх Пример' title='Код Бчх Пример' />В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи или отправки данных, и затем рассчитывается и сравнивается во время чтения получения данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно. Изменение этого бита например с 0 на 1 сообщает о возникшей ошибке. Ниже показана структурная схемы кодера для данного кода. Пример Начальные данные 1. Данные после кодирования 1. Принятые данные 1. Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка. В случае изменения состояния двух битов, возможна ситуация, когда вычисление контрольного бита совпадет с записанным. В этом случае система не определит ошибку, а это не есть хорошо. К примеру Начальные данные 1. Тогда кодом БЧХ называется n, kлинейный циклический код, в котором. Данные после кодирования 1. Принятые данные 1. В принятых данных число единиц четно, и, следовательно, декодер не обнаружит ошибку. В частности, он разработал код, который обеспечивает обнаружение и исправление одиночных ошибок при минимально возможном числе дополнительных проверочных бит. Для каждого числа проверочных символов используется специальная маркировка вида k, i, где k количество символов в сообщении, i количество информационных символов в сообщении. Например, существуют коды 7, 4, 1. Каждый проверочный символ в коде Хэмминга представляет сумму по модулю 2 некоторой подпоследовательности данных. Рассмотрим сразу на примере, когда количество информационных бит i в блоке равно 4 это код 7,4, количество проверочных символов равно 3. Классически, эти символы располагаются на позициях, равных степеням двойки в порядке возрастания первый проверочный бит на 2. Пример работы алгоритма, так что особо подробно описывать в этой статье не вижу смысла. Вместо этого приведу структурную схему кодера. Набор этих значений e. Декодер эти значения вычисляет, и если они все не равны 0 то есть не получится 0. Коды произведения. В канале связи кроме одиночных ошибок, вызванных шумами, часто встречаются пакетные ошибки, вызванные импульсными помехами, замираниями или выпадениями при цифровой видеозаписи. При этом пораженными оказываются сотни, а то и тысячи бит информации подряд. Ясно, что ни один помехоустойчивый код не сможет справиться с такой ошибкой. Для возможности борьбы с такими ошибками используются коды произведения. Принцип действия такого кода изображн на рисунке. Передаваемая информация кодируется дважды во внешнем и внутреннем кодерах. Код Бчх Пример' title='Код Бчх Пример' />Коды Боуза Чоудхури Хоквингема БЧХкоды в теории кодирования это широкий. Формальное описание 2 Построение 3 Примеры кодов. Определение. Примитивный код БЧХ, исправляющий ошибок, это блоковый. Пусть нужно найти порождающий многочлен для кода БЧХ в. БЧХ находится как их. Для конкретизации приведенной методики рассмотрим примеры. Рассмотрим 15,5 код из предыдущего примера пусть порождающий его полином. Diag_1.png' alt='Код Бчх Пример' title='Код Бчх Пример' />Нужно построить БЧХкод с длиной кодовых слов n15 и минимальным расстоянием между кодовыми словами d5. Между ними устанавливается буфер, работа которого показана на рисунке. Информационные слова проходят через первый помехоустойчивый кодер, называемый внешним, т. Здесь к ним добавляются проверочные символы, а они, в свою очередь, заносятся в буфер по столбцам, а выводятся построчно. Этот процесс называется перемешиванием или перемежением. При выводе строк из буфера к ним добавляются проверочные символы внутреннего кода. В таком порядке информация передается по каналу связи или записывается куда нибудь. Условимся, что и внутренний, и внешний коды коды Хэмминга, с тремя проверочными символами, то есть и тот, и другой могут исправить по одной ошибке в кодовом слове количество кубиков на рисунке не критично это просто схема. На приемном конце расположен точно такой же массив памяти буфер, в который информация заносится построчно, а выводится по столбцам. При возникновении пакетной ошибки крестики на рисунке в третьей и четвертой строках, она малыми порциями распределяется в кодовых словах внешнего кода и может быть исправлена. Назначение внешнего кода понятно исправление пакетных ошибок. Зачем же нужен внутренний код На рисунке, кроме пакетной, показана одиночная ошибка четвертый столбец, верхняя строка. В кодовом слове, расположенном в четвертом столбце две ошибки, и они не могут быть исправлены, т. Для выхода из этой ситуации как раз и нужен внутренний код, который исправит эту одиночную ошибку. Принимаемые данные сначала проходят внутренний декодер, где исправляются одиночные ошибки, затем записываются в буфер построчно, выводятся по столбцам и подаются на внешний декодер, где происходит исправление пакетной ошибки. Использование кодов произведений многократно увеличивает мощность помехоустойчивого кода при добавлении незначительной избыточности. P. S. Плотно занимался этой темой 3 года назад, когда писал дипломный проект, возможно что то упустил. Все исправления, замечания, пожелания пожалуйста через личные сообщения.