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

Содержание

Техническое задание

Введение

Определение числа проверочных разрядов

Нахождение образующего многочлена, построение образующей матрицы

Разработка структурной схемы кодера

Разработка принципиальной схемы кодера

Используемые микросхемы

Список литературы

Приложения

Техническое задание

Разработка восьмиразрядного кодирующего устройства на основе образующего многочлена с исправлением однократной ошибки. Скорость выдачи информации - 9600 бит/с.

Введение

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

Избыточные коды делятся на блоковые и непрерывные. В блоковых кодах информационная последовательность разбивается на отдельные блоки - информационные и проверочные. Общее число элементов кодовой комбинации в этом случае n=k+r, где k - число информационных элементов, r - число проверочных элементов. При этом кодовая комбинация передаётся целиком, а её обработка производится по отдельности для информационных и проверочных частей. В непрерывных кодах передаваемая информационная последовательность не разделяется на блоки, а проверочные элементы размещаются в определённом порядке между информационными. Процессы кодирования и декодирования здесь также имеют непрерывный характер.

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

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

Корректирующие свойства кода определяются минимальным кодовым расстоянием d₀ - расстоянием Хемминга между двумя разрешёнными кодовыми комбинациями. Для исправления одиночных ошибок расстояние Хэмминга должно быть не меньше 3.

Линейными или систематическими (n, k) - кодами называются коды, у которых проверочные элементы являются линейными комбинациями информационных. При двоичном кодировании такой линейной операцией является операция сложения "по модулю 2".

 (1)

где а₁,…., а_к - информационные разряды;

b₁,…b_r - проверочные разряды;

коэффициенты c_ij принимают значения 0 или 1 в зависимости от выбранных групп информационных элементов, участвующих в формировании проверочных.

Количество r проверочных элементов определяется исходя из обеспечения заданного расстояния Хемминга d₀. В общем случае эта задача не имеет однозначного решения. Для случая одиночной исправляемой ошибки (или однократной) формула оценки r имеет вид:

 (2)

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

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

Кодовые слова двоичного линейного кода можно представить в виде многочлена:

 (3)

где коэффициенты а_i равны 0 или 1 и соответствуют разрядам двоичного числа.

Циклические коды относятся к блоковым кодам, т.е. первые k элементов комбинации циклического кода являются информационными, а последующие r - проверочными. Следовательно, можно ввести в рассмотрение многочлен f (x) степени k-1, отображающий k-элементную комбинацию первичного кода, и многочлен r (x) степени r-1, отображающий комбинацию проверочных элементов. Тогда многочлен комбинации циклического кода

 (4)

Умножение на x^r необходимо, чтобы сдвинуть информационные элементы на r разрядов влево и тем самым высвободить справа r разрядов для записи проверочных элементов.

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

 (5)

где Q (x) - некоторый многочлен, получившийся в результате деления.

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

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

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

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

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

После циклического сдвига имеем следующую разрешенную комбинацию , которой соответствует многочлен

 (6)

Так как F₁ (x) делится на G (x) без остатка, то и для деления F₂ (x) без остатка на G (x) необходимо, чтобы двучлен (xⁿ+1) делился без остатка на G (x), т.е.

 (7)

где H (x) - проверочный многочлен (используется в декодере). Таким образом, согласно (5), образующий многочлен необходимо выбрать из числа неприводимых, входящих в разложение многочлена xⁿ+1.

Способ формирования комбинаций циклического кода, основанный на свойстве проверочного многочлена H (x). Из формулы (7), где двучлен xⁿ+1 делится без остатка на G (x) следует, что проверочный многочлен H (x) также может быть использован для задания циклического кода, если проверочный многочлен H (x) представить в виде.

Структурная схема кодера имеет вид:

Рис. 1 - Структурная схема кодера

Отметим, что число ячеек (разрядов) регистра для данного случая равно числу информационных элементов.

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

Рассмотрим принцип работы полученной системы. В исходном состоянии обратная связь разомкнута, ключ в положении 1 и в регистр вводится информационная последовательность f (x), начиная со старшего разряда. Через k-тактов после ввода информационных символов ключ переводится в положение 2, после чего в течение последующих k-тактов на выход подается информационная последовательность, а в регистре формируются проверочные элементы (символы). После этого ключ переводится в положение 1 и проверочные элементы выдаются на выход кодирующего устройства в течение последующих r тактов.

Определение числа проверочных разрядов

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

где  - количество информационных разрядов, а  - количество проверочных разрядов.

Находим необходимое количество проверочных разрядов. Для k=8 получим:

 условие не выполняется

 условие не выполняется

 условие не выполняется

 условие выполняется

Таким образом, требуется построить код (12,8).

Нахождение образующего многочлена, построение образующей матрицы

В качестве образующего выберем многочлен четвертой степени:

Построим единичную матрицу первичного кода, сдвинутую на 4 разряда влево:

Первая строка сдвинутой на 4 разряда единичной матрицы:

000 000 000. Найдем остатки от деления:

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

Разработка структурной схемы кодера

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

Рис. 2 - Обобщенная структурная схема кодера

Для кодирования взята информационная последовательность: 01 000 000. Устройство формирования кода с образующим многочленом , для которого , ,,, , имеет следующий вид:

Рис. 3 - Структурная схема кодера

В структурную схему входят:

) Четыре сдвиговых регистра;

) Два сумматора по модулю 2;

) Логический элемент ИЛИ;

) Переключатель.

Описание работы кодера по структурной схеме:

В исходном состоянии ключ находится в положении 1. На вход последовательно подаются символы , начиная со старшего разряда.

Одновременно эти символы поступают через схему ИЛИ на выход кодирующего устройства.

Через 8 тактов в регистре формируется остаток  от деления  на . Ключ переводится в положение 2, и на выход через схему ИЛИ выдаются проверочные элементы. Через 12 тактов на выходе формируется кодовая комбинация циклического кода.

Рассмотрим схему работы кодера, построив временную диаграмму при подаче на вход последовательности 01 000 000.

Таблица 1

Временная диаграмма работы кодера

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

Разработка принципиальной схемы кодера

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

В качестве схемы управления будем использовать счетчик (отсчитывающий нужное число тактов) и управляемый им мультиплексор (осуществляющий собственно переключение). В схеме используется четырехразрядный счетчик, отсчитывающий 16 тактов. Чтобы ограничить число тактов до 8 в счетчик вводится значение 8. До тех пор, пока счетчик не отсчитал 16 тактов, сигнал с выхода переполнения отсутствует, то есть устанавливается низкий уровень напряжения. Сигнал с выхода изменяет значение Т-триггера (изначально низкий уровень напряжения) на противоположное. Сигнал с инверсного выхода Т-триггера поступает на адресный вход мультиплексора, которому соответствует выход, отражающий положение 1 ключа структурной схемы (информационный вход 01 мультиплексора). Информационная последовательность подается на выход кодера и одновременно поступает на схему деления, которая в течение восьми тактов образует 4 проверочных разряда. После того, как счетчик переполнился, на выходе переполнения устанавливается высокое напряжение. Сигнал на выходе Т-триггера вновь изменится на противоположный (низкий уровень). Соответственно изменится и значение на адресном входе мультиплексора. Система перейдет в состояние, соответствующее положению ключа 2 на структурной схеме - последовательная запись проверочных разрядов из регистра схемы деления в выходной регистр. Сигналы со схемы деления начинают поступать на информационный вход мультиплексора 00. По прошествии четырех тактов проверочные разряды окажутся на выходе кодера.

Используемые микросхемы

Рассмотрим микросхемы, используемые при реализации кодирующего устройства. Будем использовать цифровые микросхемы транзисторно-транзиторной логики (ТТЛ) серии К555.

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

Особенность микросхем серии К555 - использование транзисторов с коллекторными переходами, зашунтированными диодами Шоттки. В результате транзисторы микросхем серии К555 не входят в насыщение, что существенно уменьшает задержку выключения транзисторов. К тому же они значительно меньших размеров, что уменьшает емкости их р - n - переходов.

Средняя задержка распространения элементов микросхем серии К555 примерно 15.20 нс.

Стандартные выходные уровни лог.1 составляют 2,4.2,7 В, лог.0 - 0,36.0,5 В.

Напряжение питания микросхем серий ТТЛ 5 В ± 5%.

Входы микросхем серии К555 можно подключать к источнику питания +5 В непосредственно. На печатных платах с использованием микросхем серии К555 необходима установка блокировочных конденсаторов между цепью +5 В и общим проводом. Их число определяется одним - двумя конденсаторами емкостью 0,033.0,15 мкВ на каждые пять микросхем.

К555ИЕ7.

Двоичный 4-разрядный синхронный счётчик с предустановкой, построенный на основе JK триггеров. Особенностью счетчиков является их построение по синхронному принципу, по которому все триггеры схемы переключаются одновременно от одного счетного импульса. Направление счета в счетчиках определяется состоянием на счетных входах триггера. Условное обозначение и нумерация выводов на рисунке. Параметры микросхемы описаны в таблице 2. Микросхема графически приведена на рисунке 4.

Таблица 2

Параметры микросхемы К555ИЕ7.

Рис. 4 - Условное графическое обозначение микросхемы К555ИЕ7.

Рис. 5 - Внешний вид микросхемы К555ИЕ7.

Назначение входов ИЕ7 следующее:

L - вход параллельной загрузки;

CU - прямой счет;

СD - обратный счет;- инверсный статический вход обнуления

(Сброс происходит при R = 0).

Выход PU − инверсный выход переполнения (пока счетчик не переполнился, на выходе высокий уровень).

К555ЛП12.

В качестве сумматоров по модулю 2 будем использовать применение микросхемы К555 ЛП12, которая содержит четыре двухвходовых сумматора по модулю 2. Основные параметры - в таблице 3. Микросхема графически приведена на рисунке 6.

Таблица 3

Параметры микросхемы К555ЛП12.

Микросхема содержит четыре независимых элемента "исключающее ИЛИ" со стандартными выходами ТТЛ, выполняющих функцию  в позитивной логике.

Рис. 6 - Условное графическое обозначение микросхемы К555ЛП12.

Рис. 7 - Внешний вид микросхемы К555ЛП12.

К555ТВ12.

Микросхема содержит два JK-триггера, срабатывающих по перепаду тактового импульса С. Низкий уровень напряжения U⁰ на установочном входе R устанавливает триггер в нулевое состояние вне зависимости от состояния других входов, т.е. вход R имеет наивысший приоритет. При наличии на входе R высокого уровня напряжения U¹ триггер функционирует в соответствии с таблицей истинности.

Рис. 8 - Условное графическое обозначение микросхемы К555ТВ12.

К555КП11.

Мультиплексор К555КП11 − двухканальный четырехразрядный мультиплексор, управляется сигналом адресного входа А. При низком уровне напряжения OE на выходы передается информация с соответствующих входов. Представлен на рисунке 9.

Таблица 4

Параметры микросхемы К555КП11.

Рис. 9 - Условное графическое обозначение микросхемы К555КП11.

Четырехразрядный двухканальный мультиплексор. Осуществляет коммутацию двух четырехразрядных чисел (30, 20, 10, 00 - первое число; 31, 21, 11, 01 - второе число). При наличии на входе А логического 0 на выходы передается первое число, а при наличии логической 1 - второе число.

К555ИР16.

Микросхема К555ИР16 - четырехразрядный сдвигающий регистр с возможностью асинхронной параллельной записи и последовательным считыванием. Микросхема имеет вход DR для подачи информации при последовательной записи, четыре входа D1 - D4 для подачи информации при параллельной записи, вход для подачи тактовых импульсов (вывод 9), вход параллельной записи L и прямой и инверсный выходы последнего разряда сдвигающего регистра. Сдвиг данных вправо на 1 позицию происходит согласно каждому положительному перепаду тактового импульса на входе С. Режим работы регистра определяется сигналом, поданным на вход L - при логическом 0 на нем происходит сдвиг информации, поступающей на вход DR, при логической 1 на входе L происходит параллельная запись информации со входов D1 - D4 в триггеры регистра.

Таблица 5

Параметры микросхемы К555ИР16.

Рис. 11 - Условное графическое обозначение микросхемы К555ИР16.

Рис. 12 - Внешний вид микросхемы К555ИР16.

Список литературы

1.      М. Вернер. Основы кодирования: Учебник для ВУЗов. - М.: Техносфера, 2006. - 288 с.; ил.

2.      Дмитриев В.И. Прикладная теория информации: Учеб. Для студ. вузов. - М.: Высшая школа, 1989 г.

.        Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь, 1990 г.

.        Шило В.Л. Популярные цифровые микросхемы: Справочник. - 2-е изд., исправленное. - М.: Радио и связь, 1989 г.

.        Справочник по электрическим конденсаторам / М.Н. Дьяконов, В.И. Карабанов, В.И. Пресняков и др.; Под общ. ред. И.И. Четверткова и В.Ф. Смирнова. - М.: Радио и связь, 1983. - 576 с.; ил.

Приложения

Таблица 3.2

Таблица истинности для микросхемы К555ТВ12