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

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

1. обеспечения построения простой и надежной аппаратуры, предназначенной для обработки закодированных сообщений;

2. защиты сообщений от помех (при их обработке, передаче по каналам связи, хранении); для этого используется помехоустойчивое кодирование;

3. компрессии или сжатия информации, т.е. для компактного представления данных; в этом случае применяется эффективное (оптимальное) кодирование;

4. сжатия информации с последующей защитой ее от помех; при этом используется двойное последовательное кодирование;

5. обнаружения и исправления ошибок при выполнении арифметико-логических операций; в этих случаях применяются арифметические коды

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

Кодирующее устройство (шифратор) осуществляет следующее преобразование над входным безызбыточным - разрядным кодовым словом, которое несет только полезную информацию. Кодер наращивает длину слова, увеличивая число разрядов кодового слова до п > к , при этом появляются дополнительные (избыточные, проверочные или контрольные) разряды, кроме так называемых информационных (к) разрядов, несущих полезную информацию. Таким образом, кодовое слово на выходе кодера содержит п - к = т избыточных разрядов. Содержимое дополнительных (избыточных) разрядов кодер определяет в соответствии с алгоритмом кодирования на основе содержимого информационных разрядов. Избыточная информация в помехоустойчивом кодовом слове представлена содержимым определенных информационных и дополнительных разрядов. Сама же избыточная информация - это, по существу, алгоритм формирования избыточных разрядов, т.е. алгоритм кодирования, который известен дешифратору (декодеру). То есть для дешифратора данный алгоритм кодирования является избыточной информацией - это то постоянное преобразование, что сохраняется независимо от того, какие кодовые слова передаются от источника к приемнику. Используя эту избыточную информацию, дешифратор принимает очередное слово и проверяет содержимое всех его разрядов на соответствие данному алгоритму кодирования. Если данное слово не удовлетворяет используемому алгоритму кодирования, то дешифратор делает вывод об обнаружении ошибки и в зависимости от того, "в какой степени" это соответствие не выполняется, может опознавать и исправлять некоторые ошибки.

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

10. Коды бывают: обнаруживающие и корректирующие. Корректирующие делятся на блоковые и непрерывные. При кодировании блоками, каждое исходное сообщение из массива данных замещается блоком или кодовым словом. При кодировании непрерывным кодом, новый текст не содержит слов, там кодируется вся цепочка. Блоковые коды разделяются на: Равномерные (все кодовые слова для разных сообщений имеют одинаковую длину) и неравномерные (длина слов различна).

13) Кодовое слово может передаваться от шифратора к дешифратору с ошибкой и без нее. Таким образом, возможны два варианта передачи кодового слова: правильная и неправильная. Число вариантов правильной передачи, когда разрешенное кодовое слово, проходя путь от кодера к декодеру, трансформируется само в себя, равно 2^к.

Существуют также два варианта неправильной передачи:

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

2. разрешенное кодовое слово трансформируется в запрещенное. В таких случаях дешифратор способен обнаружить ошибку, а в некоторых - и исправить. Так как каждое разрешенное слово может трансформироваться в любое запрещенное слово (число которых 2ⁿ - 2^к), то число вариантов такой ошибочной передачи 2^k(2ⁿ - 2^k).

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

2^k*2ⁿ = 2^k + 2^k(2^k- 1) + 2^k(2ⁿ-2^k).

14) 1-й способ: разбиение всех запрещенных слов на непересекающиеся подмножества по принципу принадлежности (близости) запрещенного слова к разрешенному кодовому слову. При этом "вокруг" каждого разрешенного кодового слова группируются такие запрещенные слова, которые "ближе" к нему, чем к другим разрешенным словам (рис. 2.3). В этом случае в качестве разрешенных кодовых слов следует выбирать такие, которые составляют множество элементов, удаленных друг от друга на расстояние не меньше некоторой величины (называемой минимальным хэмминговым расстоянием).

При таком способе разбиения дешифратор выносит решение в пользу того разрешенного слова, расстояние от которого до принятого слова меньше, чем до других разрешенных слов. Количество непересекающихся подмножеств запрещенных кодовых слов при этом равно числу разрешенных слов 2^k.

2 -й способ: разбиение по принципу принадлежности запрещенного кодового слова к вектору ошибки или к классу смежности. При таком разбиении декодер опознает не переданное ему слово, а вектор ошибки, которой оно оказалось поражено. Для этого декодер, учитывая содержимое избыточных и информационных разрядов, проверяет принятое слово на соответствие данному алгоритму кодирования и в результате вычисляет опознаватель (синдром) ошибки, который указывает на принадлежность принятого слова к одному из непересекающихся подмножеств запрещенных слов (классов смежности), "порожденных" определенным вектором ошибки. В такой системе кодер должен по определенным правилам кодирования определять содержимое избыточных разрядов на основе известного содержимого информационных разрядов. Эти правила или алгоритм кодирования представляют собой систему уравнений, в которых данными (известными величинами) являются значения информационных разрядов. Для определения содержимого каждого избыточного разряда применяется свое уравнение. Дешифратор проверяет на истинность каждое из этих уравнений, проверка дает либо "0", либо "1". Проверки всех уравнений дают множество нулей и единиц, называемое опознавателем ошибки. Если опознаватель состоит только из одних нулей, декодер делает вывод об отсутствии ошибки, иначе, по виду ненулевого опознавателя, декодер может определить тип ошибки, так как опознаватель указывает на принадлежность принятого слова подмножеству запрещенных слов, порожденных данным вектором ошибки.

15) Минимальное Хемминговое расстояние задает такое множество разрешенных слов, для любой пары в котором простое кодовое слово расстояние не меньше заданной величины. Величина: Вокруг каждого разрешенного кодового слова группируются такие запрещенные слова, которые ближе к нему, чем к другим разрешенным словам. Расстояние это определятся минимальным Хемминговым расстоянием. (пример – суммирование любых двоичных чисел по модулю 2)

16) Вектор ошибки – двоичное псевдослово, содержащее «1» в тех разрядах, содержимое которых искажено помехами в данном помехоустойчивом кодовом слове. Ошибки различают – коррелированные (изменяется помехой не только в одном разряде, ошибки идут потоком) и некоррелированные (смена содержимого в каком-то разряде не влияет на искажение содержимого в других словах).

17) 2^k-1>=Q – определяется число информационных разрядов; 2^n-k-1>=n – определяется число разрядов помехоустойчивого слова; n-k=m - определяется число избыточных разрядов; – определяется граница Хемминга. Дополнительных разрядов в кодовом слове должно быть столько, чтобы породить нужное число запрещенных слов или классов смежности, а именно 2^n-k-1. Число классов смежности должно быть не меньше, чем число исправляемых ошибок, поэтому – 2^n-k-1>=n

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

20) Дискретизировать функцию по времени - значит, исключить из рассмотрения множество значений этой функции в течение некоторых заданных интервалов времени. **

Рис. 1.1. Непрерывная функция непрерывного аргумента

Рис. 1.2. Гребенчатая или решетчатая функция (непрерывная функция дискретного аргумента)

Рис 1.З. Дискретная функция непрерывного аргумента

Рис. 1.4. Дискретная функция дискретного аргумента

В соответствии с данными представлениями различают сигналы следующих видов:

-непрерывные или аналоговые сигналы (функция на рис. 1.1);

-дискретно-непрерывные сигналы (функции на рис. 1.2 и 1.3);

-дискретные сигналы (функция на рис. 1,4)

Заметим, что дискретные сигналы на рис.1.4 не являются числами; это импульсы с конечным числом амплитуд.

21)

Нормированные функции отсчетов для разных отсчетных моментов не отличаются по форме, кроме смещения по оси времени (рис. 1.16). Каждая функция отсчетов равняется нулю для всех отсчетных моментов времени, кроме данного.

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

22)

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

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

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

-квантование сигнала по уровню (по амплитуде);

-дискретизация сигнала по времени;

-преобразование дискретного сигнала в двоичное число;

24) 1-й способ квантования - путем соотнесения исходного значения сигнала с ближайшим значением уровня.

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

f(t) - исходный непрерывный сигнал; f*(t) - квантованный сигнал;

ft, fi+1 - значения соседних порогов квантования (пунктир);

∆ft - шаг квантования, ∆ fi =fi+1 - fi;

Таким образом, очевидно, что в Процессе квантования неизбежно возникает принципиальная или методическая ошибка квантования - шум квантования, ее величина для момента времени t определяется в виде ∆f(t)=f(t)-f*(t)

2-й способ квантования - путем соотнесения исходного значения с ближайшим "снизу" значением уровня. В этом случае i-е пороговое значение совпадает со значением (i+1)-го уровня. Данный способ аналогичен округлению числа до ближайшего целого снизу.

Ошибка квантования всегда положительна (∆f(t) > 0) и не превышает величину шага квантования (∆f(t) < ∆f).

3-й способ квантования - путем соотнесения исходного значения с ближайшим "сверху" значением уровня. Пороги и уровни совпадают по номерам и значениям. Шум квантования всегда отрицательный (∆f(t)< 0) и не превышает величину шага квантования. Этот способ аналогичен округлению числа до ближайшего целого сверху.

Равномерным квантованием называется такое квантование, при котором шаг квантования есть постоянная величина. В большинстве случаев применяется равномерное квантование.

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

25) Различают следующие две модели помех (два типа помех):

а) аддитивные помехи формируют смесь сигнала с помехой путем алгебраического суммирования их амплитуд:

f_cn(t)=f*(t)+-f_n(t), где f„(t) - амплитуда помехи;

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

fcn(t)=k*f*(t)*fn(t) ; где K - масштабный коэффициент.

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

26) Контур управления - это контур с обратной связью, состоящий из управляю­щей, управляемой систем и цепей управления (рис. 1.1).

Таким образом, для определения роли систем в конкретном контуре управле­ния В-С-А-Д необходимо определить внешнюю по отношению к данному конту­ру и связанную с ним систему Е (рис. 1.1). Если воздействие системы Е на кон­тур В-С-А-Д основано на том, что система Е воздействует на систему А, а воз­действие контура на систему Е состоит в воздействии В на Е, то в этом случае система А является управляющей, В - управляемой, а С и Д - цепи управления.

При этом процесс управления можно рассматривать как последовательность изменений: изменений на выходе управляемой системы В, затем - на входе управляющей системы А, далее - на выходе А и на входе В и т.д.

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

Управляющая система - это система, воздействие которой приводит к тре­буемому изменению в другой системе.

Управляемая система - это система, в которой требуемые изменения вызы­ваются воздействием другой системы.

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

27) Источник (воздействия) - это система, воздействующая на другую систему контура управления.

Для цепи С источником является управляемая система В, а для цепи Д - управляющая система А.

Приемник (воздействия) - это система, на которую воздействует другая сис­тема контура управления.

Для цепи С приёмником является управляющая система А, а для цепи Д - управляемая система В.

Из этих определений следует, что цепь управления начинаемся на выходе ис­точника и заканчивается на входе приёмника

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

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

И – источник воздействия, П – приемник воздействия, <x,y,z> – цепь управления

Чтобы изменения на выходе источника приводили к изменениям на входе при­ёмника в цепи управления должен протекать некоторый физический процесс. Бу­дем считать, что физический процесс в цепи управления складывается из опреде­ленного числа (различимых) физических состояний.

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

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

30) Кодовая ассоциация - это ассоциация, состоящая из сообщений продольного множества.

В цепи управления, изображенной на рис. 1.7, кодовыми ассоциациями явля­ются, например, следующие:{x1,y1}, {y2,z2}, {х₃, z₃} и т.п.

Рис. 1.7 Коды в цепи управления

Код - это преобразование одного сообщения кодовой ассоциации в другое со­общение той же ассоциации.

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

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

Рис. 1.4. Сообщения в цепи управления: ИСТОЧНИК - источник воздейст­вия; ПРИЕМНИК - приёмник воздействия; Х= {x1,x2,x3} - оригиналы - одно из поперечных множеств сообщений; У - промежуточные сообщения; Z - образы;{x1,y1,z1} - одно из продольных множеств сообщений

С практической точки зрения следует различать «активные» и «пассивные» сообщения.

Активные сообщения или явления существуют только при наличии притока энергии и сами могут порождать другие сообщения.

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

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