Кодирование информации

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

строения блока памяти, которая COCTOJт из автоматов Мура с полной системой переходов и ьыходов. Число этих автоматов R зависит от числа состояний синтезируемого автомата по формуле К^]\о\*РМ[, где Р — число состояний в элементарном автомате, используемом для построения блока памяти; М — число состояний синтезируемого автомата. Затем юдируем состояния автомата словами длины R в алфавите {1, ..., Р}. Таким образом, если синтезируемый автомат находится в состоянии а,г={ац, ..., aiR}, то этэ означает, что первый элемент памяти находится в со:тоянии ац, второй—в состоянии ai2 и т. д., а последт-и — в состоянии «т. Способ кодирования влияет на результат, но мы ограничимся возможностью произвольного кодирования состояний. Строим закодированную таблицу переходов. Определяем структурный выходной сигнал памяти т = = (TI, ..., тн) по закодированной таблице переходов. Значения функций ть ••-, тд совпадают с соответствующими состояниями этих автоматов. Определяем структурный входной сигнал памяти D=(Db ..., DR) по закодированной таблице переходов и таблице входов элемента памяти. Последняя (табл. 1.15) представляет собой квадратную матрицу, строкам н столбцам которой соответствуют состояния, а на тересечении г-й строки и /-го столбца выписаны все входные сигналы, под действием которых автомат переходит из состояния а,; в состояние а,. Функции D,- называют функциями возбуждения автомата. Выписывая их значения для соответствующих внешних входных сигналов, указываем, какие сигналы следует подавать на ЕХОДЫ автоматов, образующих память, для того чтобы обеспечить требуе-

После кодирования состояний МПА и разметки переходов (строк) символами D,- таблица переходов расширяется до структурной таблицы переходов. Для табл. 1.26, закодировав состояния а] = 00, а2 = 01, а3=10, а4= 11, получим табл. 1.27.

Для кодирования состояний из Л1 строим специальную таблицу цх с 2Р1 строками и 2*ь столбцами. Строкам ее соответствуют двоичные р\ - разрядные слова, а столбцам — %-разрядные. В таблице \иг (табл. 5.9) размещаются

Введенные понятия используются в процедуре кодирования состояний МПА.

Строкам табл. 5.11 ставим в соответствие комбинации значений Л4, а столбцам — /ib h2, h3. Кодируя состояния из Л2, переносим в ц2 результаты кодирования состояний А1 из табл. 5.9. Как и рассчитывали, состояния из множества А (а7) = (а4, Сю} разместились в одном столбце \Л2- Далее кодируем состояния а6,..., аэ. Кодовые слова для а\ и dj, так как bz\ = {a\, a7}, должны находиться на минимальном расстоянии (Хемминга) друг от друга. Размещаем а7 в (г2 так, что ^(а7)=0 О 1 0. Аналогично получаем /С(а9)=0 011 и /С(а8)=0 .11. Состояние а6 согласно табл. 5.6 должно размещаться в одном столбце с ag таблицы ^2. Таким образом, K(i'-e)=Q 1 1 0. Нам удалось разместить состояния а6, ..., аэ в ц2 так, что их кодовые слова оказались соседними по разряду Л3 с кодовыми словами уже закодированны> состояний. Следовательно, Я^ ={/г3}. Имеем n^={/z3y/zi, Л2, Й4}. После заполнения таблицы ц2 все состояния синтезируемого МПА оказались закодированными.

В основу построения базового ТЭЗ положены одно- и многоуровневые структуры МПА, рассмотренные выше. Одноуровневая базовая схема изображена на 5.14. Ее КС построена из Г6 ПЛМ (m, r, q) и Qfi ПЗУ (т', г'). В качестве памяти использован ^-разрядный регистр RG из Л-триггеров. Функции возбуждения ?>ь ..., DRe элементов памяти делятся на две группы. Функции первой группы Ль. ..., Dh соответствуют разрядам кодовых слов состояний МПА из множества //J. Их значения формируются на выходах ПЛМЬ ..., ПЛМТб- При этом одноименные выходы функций Z)b ..., Dh всех ПЛМ объединены по схеме ИЛИ. Остальные Re,—k функций возбуждения соответствуют разрядам из множества //*2 , формируемым на выходах ПЗУ. Разбиение функций возбуждения на две группы получаем в процессе кодирования состояний МПА методом, описанным в § 5.2. В этом случае значения функций возбуждения DI, ..., DU определяются внутренними состояниями МПА и значениями входных пере-

Кодирование состояний устройства. В процессе кодирования состояний каждому состоянию устройства должна быть поставлена в соответствие некоторая кодовая комбинация. Число разрядов кода выбирается из следующих соображений: если число состояний равно М, то для обеспечения М кодовых комбинаций требуется ^-разрядный код, где k — минимальное целое число, при котором выполняется неравенство М <: 2*.

Аналогично кодированию входных и выходных сигналов каждому состоянию ат (т=1,М) абстрактного автомата в структурном автомате поставим в соответствие двоичный вектор (ет\, . -., етг, ..., етк), етге{0,1}. Для кодирования состояний а,, ..., им абстрактного автомата различными двоичными векторами должно быть выполнено условие RSsmilog; Ы. Как и ранее, будем допускать, что двоичный вектор (emi, ..., етг, .., етк) может быть заменен троичным, у которого emre{0, 1, —}, -=1,R. Закодируем состояния, входные и выходные 2* 19

После кодирования состояний формирование структурных подтаблиц Wi,..., Wv выполняется в полном соответствии с методом, рассмотренным в § 6.4. Если некоторые состояния из множеств А(ат), для которых /4(ат) = 1, отсутствуют в карте Карно, то их следует разместить в ней произвольным образом. Построенные структурные подтаблицы W0, W\ и W2 приведены в табл. 9.1. Матрицы ?! и F1 для нашего примера отсутствуют, поскольку в столбце F(am, as) подтаблицы W0 для всех строк ?>] = — D2 — Q. Обозначим через ?ПЗУ и Рпз матрицы, которые описывают функции ?>3 и D^, реализуемые ПЗУ. Тогда:

•яыми линиями). Результаты кодирования строк табл. 9.5, помеченных в столбце С, символами GI, ..., Cie, отображены в столбце K(Ci), а кодирования состояний—в столбцах К(ит) и K(as). После распределения выходных переменных формируются следующие множества: Yl={y\, уз, г/?, г/в}; Y2i = {ys, ую, г/4, у и}; У22={У4, У\ч, Уп, У\з}, k=\, 3 (т. е. на одну выходную переменную в среднем приходится 1, 3 выхода ПЛМ); У (PF) = {i/2, г/5, ув, ?>ь D2, D3}. Матрицы

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

При использовании тонкопленочной технологии для изготовления коммутационных плат с высокой разрешающей способностью предъявляются высокие требования к качеству фотошаблонов (точность совмещения слоев на поле 150 мм составляет ±5 мкм, точность выполнения линий ± 1 мкм). При тиражировании фотошаблонов удобно использовать управляемые ЭВМ координатографы (графопостроители) и фотонаборные установки. На этапе опытного-производства при составлении ограниченного числа описаний топологии невысокой сложности при объеме информации до 42 тыс. точек целесообразно применение полуавтоматической системы изготовления фотошаблонов: разработка топологии и кодирование информации вручную, обработка информации, изготовление фотошаблонов и чертежей с помощью ЭВМ. Используемое оборудование — ЭВМ типа 1020 или 1033, графопостроитель ЭМ-712, координатосъем-щик ЭМ-709, координатографы типа ЭМ-703 или КПА — обеспечивает объем работы по оснащению производства необходимыми инструментом и документацией. Система технического обеспечения в настоящее время достаточна гибка, например она позволяет отказаться от координатографов при изготовлении фотошаблонов и использовать более высокопроизводительные фотомонтажные (типа М-2005 или ЭМ-538) и микрофотонаборные (типа ЭМ-549 или ЭМ-559) установки.

По второму способу кодирование информации с помощью параметров сигнала осуществляют изменением во времени какого-либо из этих параметров по заданному закону изменения некоторого сигнала «•.>(/), который и отображает закодированную информацию. Такое изменение во времени некоторого параметра сигнала называется модуляцией сигнала по этому параметру, или, коротко, модуляцией. При этом изменяемый параметр называется модулируемым параметром, сигнал с модулируемым параметром — модулированным сигналом, а сигнал «.,.(/) — модулирующим сигналом. Если модулирующий сигнал используется непосредственно для изменения (управления) модулирующего параметра, то этот сигнал называют управляющим (как осуществляют такое управление, об этом речь впереди).

8. Дроздов Е. А., ПятибратовА. П. Автоматическое преобразование и кодирование информации. — М., 1964.

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

Кодирование информации 8 Компараторы 185

СИСТЕМЫ СЧИСЛЕНИЯ И КОДИРОВАНИЕ ИНФОРМАЦИИ

ГОСТ 10859-64 регламентирует кодирование информации на пяти-, шести-, семи- и восьмипозиционной перфоленте. Этот код предназначается в основном для ввода и вывода информации из вычислительных машин. Информацию, закодированную согласно ГОСТ 10859-64 на шести-, семи- и восьмипозиционной ленте, невозможно передать по линиям связи без предварительного преобразования.

Кодирование информации в десятичной системе счисления в настоящее время находит широкое применение в связи с развитием

26. Дроздов Е. А., Пятибратов А. П. Автоматическое преобразование и кодирование информации. М., «Советское радио», 1964.

Глава вторая. Системы счисления и кодирование информации .................. 46