Минимизация не полностью определенных переключательных функций

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

Для запрещенных входных комбинаций выходные сигналы не определены, т.е. могут принимать любые значения 0 или 1. Поэтому при синтезе КС с не полностью заданным законом функционирования можно произвольно задать значение выходных сигналов для запрещенной комбинации входных сигналов, поскольку нормальная работа схемы при этом не нарушается. Обычно выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему. Работа схем с запрещенными комбинациями входных сигналов описывается не полностью определенными ПФ, т.е. функциями, значения которых определены не на всех наборах аргументов. Поэтому минимизация не полностью определенных ПФ с помощью карт Карно сводится к такому доопределению ПФ, при котором получаются группы с максимальным числом соседних единиц в каждой группе, а число таких групп минимально. При этом ПФ будет содержать минимум букв.

53. Кодирование. Кодовое расстояние. Взвешеннные коды.

Кодирование — преобразование, изменение представления информации между различными форматами для передачи по линиям связи или хранения на носителях. Понятие кодирование применяется к процессу или алгоритму преобразования. Для самих форм представления, между которыми производится преобразование применяются понятия код и формат.

Кодовое расстояние между двумя кодовыми словами (расстояние Хэмминга) - это число позиций, в которых они отличаются друг от друга.

В применяемом двоично-десятичном коде любое одноразрядное десятичное число А может быть выражено в виде суммы:

А = OiQi + + G3Q3 + aQi,

где Qu Q2, Qs, Q4 -двоичные числа (О или 1) в соответствующих разрядах кодовой комбинации, а а±, Cg, 03, 04 - некоторые постоянные числа, то говорят, что этот код взвешенный и коэффициенты Gi, 02, 03, G4 называют весами двоичных разрядов.

Взвешенные коды обычно обозначают, перечисляя веса разрядов, начиная со старшего.

Чаще других употребляется двоично-десятичный код 8-4- 2-1. Преимущество этого кода перед другими заключается, во-первых, в том, что двоичные комбинации для одноразрядных десятичных чисел в нем такие же, как и при обычном двоичном счете, и, во-вторых, в том, что этот код однозначен: для каждого десятичного числа существует только одна соответствующая ему кодовая комбинация. Другие же коды неоднозначны.

Наряду с кодом 8-4-2-1 находят широкое применение также и другие двоично-десятичные коды. При этом взвешенные коды применяются чаще, чем невзвешенные, что объясняется тем, что взвешенные коды более приемлемы при построении цифро-аналоговых преобразователей.

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

54. Код Хемминга. Коды с определением ошибки.

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

По схеме кодирования Хемминга после каждых четырех бит данных добавляются три контрольных бита.

Код Хемминга обеспечивает исправление ошибки в одном бите и определение ошибки в двух следующих битах.

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку.

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

, где — принятый вектор,

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

55. Шифрование.

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

Согласно ГОСТ 28147-89, шифрование подразделяется на процесс зашифровывания и расшифровывания.

В зависимости от алгоритма преобразования данных, методы шифрования подразделяются на гарантированной или временной криптостойкости.

В зависимости от структуры используемых ключей методы шифрования подразделяются на

· симметричное шифрование: посторонним лицам может быть известен алгоритм шифрования, но неизвестна небольшая порция секретной информации — ключа, одинакового для отправителя и получателя сообщения;

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

Существуют следующие криптографические примитивы:

· Бесключевые

· Хеш-функции

· Односторонние перестановки

· Генераторы псевдослучайных чисел

· Симметричные схемы

· Шифры (блочные,потоковые)

· Хеш-функции

· ЭЦП

· Генераторы псевдослучайных чисел

· Примитивы идентификации

· Асимметричные схемы

· Шифры

· ЭЦП

· Примитивы идентификации

56. Точность представления числовой информации.

Точность (в технике) - степень приближения истинного значения параметра процеcса, вещества, предмета к его номинальному значению. Различают точность механической обработки, механизмов, систем автоматического управления, ЭВМ, измерения.

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

Численно точность измерения - величина, обратная относительно погрешности измерений R0; так, при R0= ± 10-5 точность измерения равна 105...3.

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

57. Алгебра отношений.

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

n-арная операция на G — это отображение прямого произведения n экземпляров множества в само множество .

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

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

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

Не все алгебраические конструкции описываются алгебраическими системами, в качестве примера иных можно упомянуть коалгебры, биалгебры, алгебры Хопфа и комодули над ними.