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

Представление информации в цифровых автоматах (ЦА).

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

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

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

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

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

Мультиплексорпередачи данных – устройство сопряжения ЭВМ с несколькими каналами связи.

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

Рисунок 5.6 - TP10MD мультиплексор дуплексный

Рисунок 5.7 – Мультиплексор

Для передачи цифровой информации по каналу связи необходимо поток битов преобразовать в аналоговые каналы, и при приеме информации из канала связи в ЭВМ выполнить обратное действие – преобразовать аналоговые сигналы в поток битов, которые может обрабатывать ЭВМ. Такие преобразования выполняет специальное устройство – модем.

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

Внешние модемы:

Рисунок 5.8 - Внешний модем модели Speedtouch 350 adsl

Рисунок 5.9 - Внешний модем модели Zyxel omni 56k com Plus

Рисунок 5.10 - Внешний модем модели Zyxel dsl Zyxel

Внутренние модемы:

Рисунок 5.11 - Внутренний модем модели Acorp pci Sprinter 56k Soft V 92

Рисунок 5.12 - Внутренний модем модели Diamond Supra 56K int

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

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

Рисунок 5.13 - Концентратор Switch D link 24 port

Рисунок 5.14 - Концентратор SB2 0 D Link dub

Рисунок 5.15 - Концентратор H7 usb звезда

Рисунок 5.16 - Миниатюрный концентратор

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

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

Существуют локальные и дистанционные повторители. Локальные повторители позволяют соединять фрагменты сетей, расположенные на расстоянии до 50 м., а дистанционные – до 2000 м.

Рисунок 5.17 - Повторитель RS485 Модель М2108

Рисунок 5.18 - Повторитель Siemens gigaset repeater

Рисунок 5.19 - Промежуточный повторитель

Рисунок 5.20 - Повторитель Linksys Wireless Range Expander 802.11 gWRE54G

Коды как средство тайнописи появились в глубокой древности. Из­вестно, что еще древнегреческий историк Геродот к V в. до н.э. приводил примеры писем, понятных лишь адресату. Секретная азбука использовалась Юлием Цезарем. Над созданием различных секретных шифров работали такие известные ученые средневековья, как Ф. Бэкон, Д. Кардано и др. Появлялись очень хитрые шифры и коды, которые, однако, с течением времени расшифровывались и переставали быть секретом. Первым кодом, предназначенным для передачи сообщений по каналам связи, был код С. Морзе, содержащий разное количество символов для кодирования букв и цифр. Затем появился код Ж. Бодо, используемый в телеграфии, в котором все буквы или цифры содержат одинаковое количество символов. В качестве символов может выступать наличие или отсутствие (пробел) импульса в электрической цепи в данный момент.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Код строится следующим образом: буквы алфавита сообщений выпи­сываются в таблицу в порядке убывания вероятностей. Затем они разделя­ются на две группы так, чтобы суммы вероятностей в каждой из групп бы­ли по возможности одинаковы. Всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним — 0. Каждая из получен­ных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

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

Таблица 4.1 - Алфавит из восьми букв

Буквы	Вероятности	Кодовые комбинации
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

Вычислим энтропию набора букв:

и среднее число символов на букву

где п(z_i) — число символов в кодовой комбинации, соответствующей букве z_i. Значения z и lср не очень различаются по величине.

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

Множество вероятностей в предыдущей таблице можно было разбить иначе (Таблица 4.2).

Таблица 4.2 - Множество вероятностей

Буквы	Вероятности	Кодовые комбинации
Z1	0,22
Z2	0,20
Z3	0,16
Z4	0,16
Z5	0,10
Z6	0,10
Z7	0,04
Z8	0,02

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

От указанного недостатка свободна методика Д. Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

Таблица 4.3 – Код Д. Хаффмена

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

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

Рисунок 6.1 - Кодовое дерево

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

Z1	Z2	Z4	Z5	Z6	Z7	Z8

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

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

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

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

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

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

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

+

100101100

110110101

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

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

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

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

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

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

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

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

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

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

Если принятая запрещенная комбинация принадлежит подмножеству M_i, то считается, что передана комбинация A_i (Рисунок 4.2).

Рисунок 6.2 – Схема передачи комбинаций

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

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

Дата добавления: 2014-01-06