Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Следствие доказано.

§26. Мультиплексор. Верхняя оценка сложности мультиплексора. Метод Шеннона

Определение 1. Мультиплексором _n порядка n называется схема из функциональных элементов с n + 2ⁿ входами , и 1 выходом z такая, что если на входы x₁, …, x_n поступает набор (₁, …, _n), то .

Теорема 5. Существует мультиплексор _n порядка n с числом элементов

.

Доказательство. Заметим, что задачу решает функция

.

Для её вычисления достаточно использовать один дешифратор, 2ⁿ конъюнкций и 2ⁿ – 1 дизъюнкций и

.

Теорема доказана.

Определение 2. Сложностью L (S) схемы S называется число элементов в ней.

Определение 3. Сложностью функции алгебры логики f (x₁, …, x_n) называется .

Определение 4. Функцией Шеннона L(n) для схемы из функциональных элементов называется .

Обозначения: g (n) ≲ h (n)  g (n)  h (n)·(1 +o(1)); g (n) ≳ h (n) 
 g (n)  h (n)·(1 +o(1)).

Определение 5. Универсальным многополюсником U_n порядка n называется схема из функциональных элементов с n входами и выходами, на которых реализуются все функций от x₁, …, x_n.

Теорема 6. Минимальная сложность универсального многополюсника порядка n равна .

Доказательство. 1) Очевидно, что , так как всего функций алгебры логики от n переменных, отличных от входных переменных, ровно .

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

Теорема 7. ≲ .

Доказательство. Рассмотрим произвольную функцию f (x₁, …, x_n). Выберем некоторое натуральное k (1  k  n) и рассмотрим разложение взятой функции по первым k переменным:

.

Построим схему из функциональных элементов из универсального многополюсника U_n–k порядка n – k от базовых переменных x_{k + 1}, …, x_n и мультиплексора _n порядка n с адресными переменными x₁, …, x_k, на информационные входы которого подаются те выходы U_{n – k}, на которых реализуются функции . Мультиплексор можно построить так, что его сложность не превзойдёт , а универсальный многополюсник так, что его сложность будет не больше, чем . Итак,

.

Полагая (при этом k  n – log₂(n – 2log₂n) + 1, а n – k  log₂(n – 2log₂n)), получим, что

и в итоге

≲ .

Теорема доказана.

Определение 6. Пусть  (L, n) — число всех попарно неизоморфных схем из функциональных элементов с входными переменными x₁, …, x_n и выходной переменной z₁, сложность которых не превосходит L.

Лемма 5. В функциональном базисе {&, , }  (L, n)  (L + n)^{2L + 4}.

Доказательство. Можно выбрать целые неотрицательные числа L₁, L₂, L₃ так, чтобы их сумма не превосходила L, не более, чем (L + 1)³ способами. Можно взять L₁ конъюнкций, L₂ дизъюнкций, L₃ отрицаний, а затем каждый вход каждого из них «присоединить» к выходу некоторого другого функционального элемента или к входу схемы не более, чем (L + n)^2L способами, и пометить в качестве выхода одну из не более, чем L + n точек.

Тогда  (L, n)  (L + 1)³·(L + n)^2L·(L + n)  (L + n)^{2L + 4}. Лемма доказана.

Теорема 8. Для функции Шеннона L (n) справедливо ≳ .

Доказательство. Так как, по определению, схемами сложности не более L (n) реализуются все функции от n переменных, то , но в то же время согласно лемме  (L, n)  (L + n)^2L+4. Следовательно, . Так как ≲ ,то начиная с некоторого номера n, n + L (n)  2ⁿ и , откуда ≳ . Теорема доказана.

§27. Шифратор. Верхняя оценка сложности шифратора

Определение. Шифратором D_n порядка n называется схема из функциональных элементов с 2ⁿ входами и n выходами y₁,y₂,…,y_n такая, что если на вход поступает набор с одной единицей по переменной x_i, то на выходе образуется набор (₁, ₂, …, _n)₂ = i.

Теорема 9. Существует шифратор D_n порядка n со сложностью, не превосходящей

n·2^{n – 1}.

Доказательство. Задачу решает система функций

(например, ). Всего в каждой дизъюнкции 2^{n – 1} слагаемых, следовательно, необходимо 2^{n – 1} – 1 дизъюнкторов, всего таких функций надо реализовать n, то есть получаем оценку сложности шифратора L (D_n)  (2^{n – 1} – 1) · n < n · 2^{n – 1}. Теорема доказана.

Глава IV. Основы теории кодирования

§28. Алфавитное кодирование. Теорема Маркова о взаимной однозначности алфавитного кодирования

Определение 1. Пусть A = {a₁, a₂, …, a_r} — исходный алфавит, B = {b₁, b₂, …, b_m} — кодирующий алфавит и

A^* =   A  A²  A³  …  Aⁿ  …,
B^* =   B  B²  B³  …  Bⁿ  ….

Тогда алфавитным кодированием A^*  B^* назовём отображение
 : A  B^* такое, что a_i  B_i. Множество {B₁, B₂, …, B_r} при этом называется множеством кодовых слов (или просто кодом). При этом

.

Определение 2. Кодирование A^*  B^* называется взаимно однозначным (декодируемым, разделимым), если для любых слов и выполняется .

Определение 3. Код называется равномерным, если длины всех его кодовых слов одинаковы.

Утверждение 1. Любой равномерный код является взаимно однозначным.

Определение 4. Код называется префиксным, если никакое кодовое слово не является началом другого.

Утверждение 2. Любое префиксное кодирование является взаимно однозначным.

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

Утверждение 3. Любое постфиксное кодирование является взаимно однозначным.

Определение 6. Слово называется неприводимым, если декодируется неоднозначно, однако, при выбрасывании из любого связного непустого куска получается слово, которое декодируется не более, чем одним способом.

Теорема 1 [Марков А. А.]. Пусть : a_i  B_i (i = 1, 2, …, r) — некоторое кодирование. Пусть W — максимальное число кодовых слов, которые «помещаются» подряд внутри кодового слова. Пусть l_i — длина слова B_i и . Тогда если кодирование  не взаимно однозначно, то существуют два различных слова a'  A^*, a''  A^*,

, и  (a') =  (a'').

Доказательство. Пусть  не является взаимно однозначным. Тогда существует некоторое слово , которое допускает две расшифровки. Если слово не является неприводимым, то выбрасывая из куски несколько раз, получим неприводимое слово ; иначе, положим . Очевидно, это всегда можно сделать. Рассмотрим любые две декодировки слова . Разрежем слово в концевых точках кодовых слов каждого из разбиений. Слова нового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементарными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения).

Лемма. Если — неприводимое слово, то все слова ₁, ₂, …, _m II класса различны.

Доказательство. Пусть ' = ''. Тогда, очевидно, слово не будет неприводимым, поскольку при выкидывании отрезка между ' и '', вместе с любым одним из этих слов, получим снова две различные расшифровки этого слова (проверьте). Лемма доказана.

Таким образом, все ₁, ₂, …, _m разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит

(l₁ – 1) + (l₂ – 1) + … + (l_r – 1) = L – r.

Слова из второго класса разбивают слово не более чем на L – r + 1 кусков. Рассмотрим пары соседних кусков. Тогда согласно одному разбиению в одной половинке уложится не более одного кодового слова, а в другой — не более W (согласно второму разбиению ситуация симметрична). Всего пар кусков не больше, чем

,

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

§29. Неравенство Макмиллана

Теорема 2 (неравенство Макмиллана). Пусть задано кодирование  : a_i  B_i (i = 1, 2, …, r) и пусть в кодирующем алфавите B — q букв и длина (B_i) = l_i (i = 1, 2, …, r). Тогда если  взаимно однозначно, то

.

Доказательство. Положим . Тогда для любого натурального n

.

Обозначая и приводя подобные члены, получим, что эта сумма равна .

Лемма. c_k  q^k (k).

Доказательство. За c_k обозначено, очевидно, число наборов (i₁, …, i_n) (1  i_j  r), для которых . Но такой сумме соответствует слово и

.

В силу того, что кодирование взаимно однозначно, различным наборам соответствуют различные сообщения, а различных сообщений длины k в алфавите из q букв не более q^k  k (c_k  q^k).

Лемма доказана.

Согласно лемме . Устремляя n к бесконечности, получаем x  1. Теорема доказана.

§30. Существование префиксного кода с заданными длинами кодовых слов

Характеристики

Список файлов лекций