1.15. Линейные функции

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

Функция называется линейной [8], если она удовлетворяет принципу суперпозиции

где константы; некоторое поле.

Полем называется множество элементов для которых определены две операции, называемые сложением и умножением и выполняются аксиомы:

- замкнутость;

— ассоциативные законы;

- коммутативные законы;

- дистрибутивный закон;

существование единичных элементов относительно операций сложения и умножения (для операции сложения единичный элемент называется нулем, а для операции умножения — единицей);

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

На основании этих аксиом можно доказать, что каждый элемент поля имеет единственный противоположный и единственный обратный элементы, а также, что

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

В теории цифровых автоматов могут быть использованы только конечные поля, т. е. поля, множество элементов которых конечно. Широкое применение в теории и практике проектирования цифровых устройств находят поля Галуа в которых в качестве бинарных операций используются операции сложения и умножения целых чисел по модулю где простое число [13, 16]. Такие поля содержат элементов: Напомним, что число X по модулю равно остатку от деления данного числа на

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

где или Данные функции удовлетворяют

Таблица 1.7. (см. скан) Сложение и умножение по модулю 2

Таблица 1.8. (см. скан) Сложение и умножение по модулю 3

Таблица 1.9. (см. скан) Сложение и умножение по модулю 5

определению линейных функций (1.90), если положить

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

Согласно определению (1.90), линейными функциями являются функции

где и переменные принимают значения из поля

Комбинационные схемы, выполняющие операции сложения и умножения по модулю называются линейными. При значении проблема синтеза линейных КС отсутствует, так как ЛЭ И и сумма по модулю два выпускаются в виде И С. При значениях необходимо синтезировать типовые линейные КС, выполняющие операции сложения -ичных чисел и умножения их на константы по модулю Данная задача решена в § 6.15.