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

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

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

На практике при кодировании дискретных сообщений широко применяется двоичная система счисления.

6.1.2.2. Корректирующие коды

Говорят, что в канале произошла ошибка кратности q, если в кодовой комбинации q символов приняты ошибочно. Легко видеть, что кратность ошибки есть не что иное, как расстояние Хэмминга между переданной и принятой кодовыми комбинациями, или, иначе, вес вектора ошибки.

Рассматривая все разрешенные кодовые комбинации и определяя кодовые расстояния между каждой парой, можно найти наименьшее из них d = min d(i; j), где минимум берется по всем парам разрешенных комбинаций. Это минимальное кодовое расстояние является важным параметром кода. Очевидно, что для простого кода d=1.

Обнаруживающая способность кода характеризуется следующей теоремой. Если код имеет d>1 и используется декодирование по методу обнаружения ошибок, то все ошибки кратностью q ³ d, то одни из них обнаруживаются, а другие нет.

Таким образом, применение достаточно эффективных (а значит, и достаточно длинных) кодов при табличном методе кодирования и декодирования технически невозможно.

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

6.1.2.3. Линейные коды

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

Если записать k линейно-независимых блоков в виде k строк, то получится матрица размером n ´ k, которую называют порождающей или производящей матрицей кода G.

Множество линейных комбинаций образует линейное пространство, содержащее 2 k блоков, т.е. линейный код, содержащий 2 k блоков длиной n, обозначают (n, k). При заданных n и k существует много различных (n, k)-кодов с различными кодовыми расстояниями d, определяемых различными порождающими матрицами. Все они имеют избыточность e k =1-k/n или относительную скорость R k =k/n.

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

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

6.1.2.4. Совершенные и квазисовершенные коды

Число известных совершенных кодов ограничено кодами Хэмминга значности и бинарным циклическим кодом Голея.

Класс квазисовершенных кодов значительно шире, чем класс плотно упакованных кодов.

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

6.1.2.5. Циклические коды

Рассмотрим данный класс кодов подробнее. Название циклических кодов связано с тем, что каждая кодовая комбинация, получаемая путем циклической перестановки символов, также принадлежит коду. Так, например, циклические перестановки комбинации 1000101 будут также кодовыми комбинациями 0001011, 0010110, 0101100 и т.д.

Представление кодовых комбинаций в виде многочленов F(x) позволяет установить однозначное соответствие между ними и свести действия над комбинациями к действию над многочленами. Сложение двоичных многочленов сводится к сложению по модулю 2 коэффициентов при равных степенях переменной x. Умножение производится по обычному правилу умножения степенных функций, однако полученные коэффициенты при данной степени складываются по модулю 2. Деление осуществляется, как обычное деление многочленов, при этом операция вычитания заменяется операцией сложения по модулю 2. Циклическая перестановка кодовой комбинации эквивалентна умножению полинома F(x) на x с заменой на единицу переменной со степенью, превышающую степень полинома.

Особую роль в теории циклических кодов играют неприводимые многочлены G(x), т.е. полиномы, которые не могут быть представлены в виде произведения многочленов низших степеней.

Представляем информационную часть кодовой комбинации длиной k в виде полинома Q(x).

Делим полином Q(x)x r на порождающий полином G(x) степени r, при этом получаем частное от деления C(x) такой же степени, что и Q(x).

Полином F(x) делится без остатка на G(x), т.е. представляет собой разрешенную комбинацию циклического (n,k)-кода.

Таким образом, разрешенную кодовую комбинацию циклического кода можно получить двумя способами: умножением кодовой комбинации простого кода C(x) на полином G(x) или умножением кодовой комбинации Q(x) простого кода на одночлен x r и добавлением к этому произведению остатка R(x).

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

Умножение Q(x) на x r эквивалентно повышению степени многочлена на r. Q(x) = ® 10111.

Формирование проверочной группы осуществляется в процессе деления Q(x)x r на G(x).

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

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

6.1.2.6. Прочие классы кодов

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

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

6.1.2.8. Системы с обратной связью

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

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

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

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

Источник

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

Дата добавления: 2015-08-14 ; просмотров: 1068 ; Нарушение авторских прав

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

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

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

Количество разрядов в кодовой комбинации называется значностьюкода или длиной. Количество единиц в коде называют весом кодовой комбинации. Например, кодовая комбинация 1100101 характеризуется значностью и весом V = 4.

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

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

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

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

Помехоустойчивость кодов обеспечивается за счет введения избыточности, т.е. из общего количества символов комбинации для передачи используется только часть – m символов, при этом m m разрешенных комбинаций. Группа комбинаций называется запрещенной. Для кодирования N ’ событий требуется n=log₂N’ двоичных символов. Такой код, содержащий в себе кроме информационных разрядов еще и контрольные называется систематическим. В контрольные разряды записывается код, характеризующий состояние информационных разрядов. При этом абсолютная избыточность выражается количеством контрольных разрядов – k, а относительная избыточность отношением – k/n, где n=m+k – общее количество разрядов в кодовом сообщении.

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

. (2.1)

Тогда полная вероятность искажения кодовой комбинации будет равна:

. (2.2)

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

1) N случаев безошибочной передачи;

2) N(N-1) случаев перехода в другие разрешенные комбинации;

Доля обнаруживаемых ошибочных комбинаций составляет

(2.3)

Доля исправляемых ошибочных комбинаций от общего числа обнаруживаемых ошибок составляет:

. (2.4)

Избыточность кода можно ввести разными путями. Рассмотри один из путей эффективного кодирования. В ряде случаев буквы сообщений преобразуются в последовательность символов. Учитывая статистические свойства источника сообщения, можно минимизировать среднее число двоичных символов, требующихся для выражения одной буквы сообщения, что при отсутствии помех позволит сократить время передачи. Такое эффективное кодирование базируется на теореме Шеннона для каналов без помех, в которой доказано, что сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины. Теорема не указывает конкретного способа кодирования, но из нее следует, что при выборе каждого символа кодовой комбинации необходимо стараться, чтобы он нес максимальную информацию [3]. Следовательно, каждый символ должен принимать значения 0 или 1 по возможности с равными вероятностями и каждый выбор должен быть независим от значений предыдущих символов.

При отсутствии статистической взаимосвязи между буквами конструктивные методы построения эффективных кодов были даны впервые К. Шенноном и Н. Фано. Их методики существенно не различались, поэтому соответствующий код получил название кода Шеннона – Фано, который подробнее будет рассмотрен в разделе 2.3.1.

Рассмотрим построение кода, обнаруживающего все ошибки кратностью и ниже. Из множества всех возможных комбинаций нужно выбрать разрешенные комбинации так, чтобы любая из них в сумме по модулю 2 с вектором ошибки с весом m_t = t не выдавала бы другой разрешенной комбинации. Для этого необходимо, чтобы кодовое расстояние удовлетворяло условию: d_min ≥ t+1. В качестве примера возьмем код со значностью n=3. Все возможные комбинации кода представлены в таблице 2.1.

Матрица расстояний между всеми возможными комбинациями имеет вид:

Выберем из всех возможных комбинаций разрешенные такие, чтобы d=2. Такому условию соответствуют . Запрещенные комбинации: а₂, а₃, а₅, а₈. Такой код позволяет обнаружить однократные ошибки.

Рассмотрим построение кода, устраняющего однократные ошибки. Возьмем в качестве разрешенной комбинации а₁=000. При наличии однократных ошибок комбинация а₁ может перейти в одну из запрещенных комбинаций а₂=001, а₃=010, а₅=100. Это означает, что в случае приема одной из них выносится решение, что передана исходная комбинация а₁ с ошибкой. При разрешенной комбинации а₄=011, при условии, что и d=2, подмножество ее запрещенных комбинаций составляет: , при а₃=010, а₂=001, а₈=111. Таким образом, подмножества запрещенных комбинаций для а₁ и а₄ пересеклись, имея два общих элемента а₂ и а₃, т.е. . В этом случае нельзя однозначно установить исходную кодовую комбинацию.

Если же в качестве второй кодовой комбинации выбрать а₈=111, то d=3 и в случае однократных ошибок ей будет соответствовать подмножество: при а₄=011, а₆=101, а₇=110. В этом случае подмножества не пересекаются и следовательно, обеспечивается устранение однократных ошибок.

В общем случае, для устранения ошибок кратности кодовое расстояние должно удовлетворять условию:d_min≥2δ+1. Установлено, что для исправления всех ошибок кратности δ и обнаружения всех ошибок кратности ( ), кодовое расстояние должно удовлетворять условию: d_min≥t+δ+1.

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

Источник

Информационные основы контроля работы цифрового автомата.

Тема: Информационные основы контроля работы цифрового автомата

1. Информационные основы контроля работы цифрового автомата

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

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

4. Систематические коды

5. Кодирование по методу четности-нечетности

Тема: Информационные основы контроля работы цифрового автомата.

1. Информационные основы контроля работы цифрового автомата

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

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

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

1) возникающие из-за погрешностей в исходных данных;

2) обусловленные методическими погрешностями;

3) появляющиеся из-за возникновения неисправностей в работе машины.

Первые два вида ошибок не являются объектом для работы системы контроля. Конечно, погрешности перевода или представления числовой информации в разрядной сетки автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная её максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно.

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

· профилактический контроль, задача которого – предупреждение появления ошибок в работе;

· оперативный контроль, задача которого – проверка правильности выполнения машиной всех операций.

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

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

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

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

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

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

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

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

Однако в теореме Шеннона не говорится о том, как нужно строить помехоустойчивые коды.

На этот вопрос отвечает теория помехоустойчивого кодирования.

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

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

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

Напомним, что двоичный код – это код с основание m =2.

Количество разрядов n в кодовой комбинации принято называть длиной или значностью кода. Каждый разряд может принимать значение 0 или 1. Количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают .

Например, кодовая комбинация 100101100 характеризуется значностью n =9 и весом =4.

100101100

Полученная в результате суммирования новая кодовая комбинация характеризуется весом =4. Следовательно, расстояние между исходными кодовыми комбинациями d =4.

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

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

Вес вектора ошибки характеризует кратность ошибки. Сумма по модулю для искажений кодовой комбинации и вектора ошибки дает исходную неискаженную комбинацию.

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

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

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

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

(7.27)

Источник ← С чем связывается необходимость хранения архивных документов appdata local temp можно ли удалить содержимое windows 10 → Вам также понравится код окпд 2 масло для триммера 29.09.202312.05.2023 admin 0 город дураков камера хранения коды 04.09.202309.05.2023 admin 0 гибдд код подразделения 1150401 03.09.202309.05.2023 admin 0 Добавить комментарий Отменить ответ Ваш адрес email не будет опубликован. Обязательные поля помечены * Комментарий * Имя * Email * Сохранить моё имя, email и адрес сайта в этом браузере для последующих моих комментариев.