информатика. Документ Microsoft Word555. Задание Составьте словарь терминов по теме. Алгоритм
 Скачать 111.02 Kb.
|
|
Кодирование источника - использование в рамках заданного алфавита кодов переменной длины с целью уменьшения числа символов в сообщении до минимума необходимого, для представления всей информации сообщения или, по крайней мере, для обеспечения условий такого сокращения. При кодировании источника конкретный код выбирается на основе характеристик источника сообщения (т.е. относительных вероятностей появления различных знаков алфавита в исходной программе), а не на основе характеристик канала, по которому, в конечном счете будет передано сообщение. Основная идея сжатого кодирования заключается в представлении наиболее вероятных символов сообщения кодами наименьшей длины, а менее вероятных - кодами большей длины с тем, чтобы средневзвешенная по вероятности длина кода была минимальной в пределах, задаваемых неравенством Крафта . Наиболее широко используется кодирование по методу Шеннона-Фано и кодирование по методу Хаффмена. Первый метод проще в вычислительном отношении, второй - эффективен при заданном расширении источника. Кодирование по алгоритму Хаффмена - как правило, двоичное кодирование элемента конечного множества A = {a1, a2,..., aN}, для каждого элемента ai которого предполагается известной вероятность pi появления в сообщении. Для этого метода двоичного кодирования выполняется префиксное условие, а кроме того, средняя длина получаемых сообщений оказывается минимальной. Таким образом, элемент ai с высокой вероятностью появления в сообщении будет кодироваться короткой двоичной строкой, а элемент с малой вероятностью появления – более длинной строкой. Кодирование по методу Шеннона-Фано - относится к методам эффективного кодирования некорреляционной последовательности знаков. Код строят следующим образом: знаки алфавита сообщений выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве первого символа приписывают 0, а всем нижним -1. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному знаку. Кодирование по этому методу не всегда приводит к однозначному по строению кода. От указанного недостатка свободно кодирование по алгоритму Хаффмена. Кодовое слово - см. блочный код. Коды Адамара - коды, построенные на основе матриц Адамара. Это семейство квадратных матриц H, удовлетворяющих соотношению т H * H = c * I, т здесь H -транспонированная матрица H, I - единичная матрица, элементы которых могут принимать два значения: +1 или -1,c -скалярная константа. Базой для построения кода являются строки матрицы Адамара, которые образуют ортонормальный базис. Кодово-импульсная модуляция - используемый в кодере-декодере метод преобразования аналогового сигнала в поток цифровых двоичных сигналов. Амплитуда аналогового сигнала преобразуется в дискретную форму. Для представления преобразованной величины выбирается соответствующий цифровой код. Цифровой код передается в пункт приема, где он используется для формирования аналогового выходного сигнала. В целях сокращения объемов данных, которые передаются между отправителем и получателем сообщений, используется техника кодирования, основанная на известных характеристиках аналогового сигнала. Количество информации - мера уменьшения неопределенности ситуации вследствие того, что становится известным исход другой ситуации. Коммутатор - комбинационная схема, которая коммутирует один из m входов с n выходами при условии, что Компрессия данных - любой из многих методов в теории информации, спомощью которого производится кодирование данных с целью сокращения их избыточности. Аналогичные методы используются и при регистрации информации. Методы сжатия позволяют, например, уменьшать объем буквенного текста в 2-5 раз. По существу, сжатие данных - это кодирование источника. Методы сжатия широко используются при передаче и хранении изображений. Конечная последовательность, список - некоторая ограниченная последовательность пунктов (x , x , ..., x ), где n > 0. Если n = 0, список не имеет позиций и называется неопределенным (или пустым) списком. При отсутствии каких-либо оговоренных условий позиции списка могут иметь произвольную структуру. В частности, любая позиция может также представлять собой список, называемый в этом случае подсписком. Если список имеет один и более подсписков, его называют списковой структурой .Список без подсписков называют последовательным списком. Контроль по избыточности - контроль, выполняемый с помощью резервированных технических средств или избыточной информации и обеспечивающий выдачу сведений о наличии определенных ошибок. Контрольная сумма, метод контрольной суммы - простой метод обнаружения ошибок, основанный на анализе некоторого набора данных или участка программы. Если этот набор представляет собой совокупность блоков длиной m бит, то берется сумма по модулю n, где n = 2 , и ставится в конец набора. Позднее (например, после пересылки набора данных в другое место) можно осуществить повторное вычисление контрольной суммы; при этом будут выявлены наиболее простые (одиночные) ошибки на уровне битов. Простейшим вариантом метода (m =1, n =2) является контроль по четности. Контрольный двоичный разряд, контрольное число - функция, которая вычисляется с целью обеспечения контроля группы двоичных величин (например, слов, байтов или символов) путем получения сумм битов в этой группе по модулю 2. Получаемая сумма представляет собой избыточную величину и называется контрольным разрядом. Этот разряд равен нулю, если число единиц в группе четное, и равен единице, если число единиц в группе было нечетным. Такой подсчет четности приводит к расширению группы двоичных величин (исходная группа плюс контрольный разряд) для получения четного числа единиц. Это свойство называется четностью. В некоторых случаях, исходя из особенностей аппаратного обеспечения, желательно иметь нечетное число единиц в расширенной группе, и контрольный разряд выбирается так, чтобы общее число единиц было нечетным. Это свойство группы двоичных величин называется нечетностью. Коэффициент сжатия - отношение длин сообщения до и после его сжатого кодирования (в общем случае такое кодирование выполняется для укорачивания сообщений). Критерий сложности - средство измерения объема ресурсов, используемых в процессе вычисления. В процессе вычисления с помощью любой машины Тьюринга могут использоваться различные ресурсы, например, пространство и время. Эти ресурсы формально могут быть определены следующим образом. Пусть заданы программа M машины Тьюринга и входная цепочка x, тогда временной ресурс Time (M, x) определяется как число шагов в вычислении M на x до останова M. Время будет неопределенным (то есть равным бесконечности), если M не останавливается на x. Временная сложность определяется как целочисленная функция, где T (n) = max (Time (M, x) : |x| = n) для неотрицательного целого числа n. Аналогичным образом пространственный ресурс Space (M, x) определяется как число квадратов ленты, используемых M на x, а пространственная сложность S - как S (n) = max (Space (M, x) : |x| = n). Однако, для того чтобы не путать пространство, необходимое для работы, с пространством, выделяемым для входной цепочки x, иногда предполагается, что машина имеет ленту ввода, работающую только на считывание, а Space (M, x) определяется как число квадратов (куда можно записывать данные), используемых M на x. Можно также определить более общие критерии сложности, в которых сочетаются многие свойства, присущие как времени, так и пространству. Лексикографический порядок (поиск) - порядок слов в словаре, определяемый последовательностью букв алфавита. В более общем случае рассматривается множество S, строго упорядоченное отношением 0 имеется множество T n-кортежей: (x , x , ..., x ) с элементами x S. Тогда отношение упорядочения этих кортежей можно определить так, что (x , ..., x ) < (y , ..., y ) тогда и только тогда, когда x < y или существует некоторое k, 1 < k < n, для которого x = y при 1 < i < k, x < y . Множество T лексикографически упорядочено, если кортежи расположены в соответствии с указанным отношением. Рассмотренное понятие можно обобщить для строк неодинаковой длины. При этом порядок строк будет совпадать с порядком слов в словаре. Линейный канал - канал связи, в котором информационный сигнал аддитивно смешивается с помехой и в результате образует выходной сигнал. В q-ном линейном канале с конечным числом q значений амплитуд сигналы складываются по модулю q; в двоичном случае q =2 - это приводит к тому же результату, что и выполнение операции исключающее ИЛИ над этими сигналами. Логическое кодирование - представление символов алфавита последовательностями логических значений. Это кодирование эквивалентно двоичному кодированию. Марковская цепь - последовательность дискретных значений случайных переменных, в которой каждый член последовательности с определенной степенью вероятности зависит только от предшествующих. В случае эргодической марковской цепи ее элементы в любой момент обладают одними и теми же статистическими свойствами. Мера информации - количественная или качественная оценка информации в сообщении. Mера Хартли - аддитивная двоичная логарифмическая мера, позволяющая вычислять количество информации в двоичных единицах (бит)по формуле I = n log h, 2 где n - например, длина числа (количество разрядов), а h - основание системы счисления, в которой представлено число. В качестве n может выступать число ячеек памяти, а в качестве h – емкость ячейки памяти. Аддитивная мера удобна тем, что она обеспечивает возможность сложения и пропорциональность количества информации к длине числа n (предложена Р.Хартли в 1928 г.). Mодель Шеннона - общепринятая модель, предложенная К.Э.Шенноном в 1948 г., в которой имеется источник информации, посылающий сообщение приемнику информации с использованием средства связи или механизма связи, называемого каналом. Согласно Шеннону, "основной проблемой связи является точное или приблизительное воспроизведение в одной точке сообщения, переданного из другой точки". В общем случае канал искажает сообщение и добавляет к нему помехи. Для устранения искажений и уменьшения воздействия помех до приемлемого уровня между источником информации и каналом помещается кодер, а между каналом и пунктом приема информации помещается декодер. Источник посылает передаваемое сообщение, которое кодируется в передаваемый сигнал; этот сигнал посылается по каналу. В результате в месте приема появляется принимаемый сигнал, который декодируется и дает принимаемое сообщение; это сообщение прибывает в пункт приема информации. Считается, что в канале действует источник помех, который в дополнение к передаваемому сигналу вводит свою "информацию". Назначением кодирующего и декодирующего устройств является формирование принимаемого сообщения, достаточно точно совпадающего с передаваемым сообщением, несмотря на влияние "информации", поступающей от источника помех. Mодем - модулятор + демодулятор - устройство, способное осуществлять модуляцию и демодуляцию информационных сигналов. Модемы используются для подключения цифровых устройств к линиям передачи аналоговых сигналов. Mодуляция - процесс изменения одного сигнала, называемого несущим, в соответствии с формой некоторого другого сигнала. Несущий - это обычно аналоговый сигнал, выбираемый так, чтобы он наилучшим образом согласовывался с характеристиками конкретной системы передачи. Сигналы и способы модуляции могут сочетаться друг с другом с целью получения комбинированных сигналов, переносимых по нескольким независимым информационным каналам. К основным типам модуляции относятся: а) амплитудная модуляция (АМ), при которой сигнал несущей из меняется по мощности или амплитуде. Эта форма модуляции в системах передачи данных в чистом виде используется сравнительно редко; б) частотная модуляция (ЧМ), при которой изменяется частота несущей. Такой способ часто применяется в модемах; в)фазовая модуляция (ФМ), при которой изменяется фаза волны несущей. Этот способ модуляции часто используется в сочетании с амплитудной модуляцией в высокоскоростных модемах; г) импульсно-кодовая модуляция (ИКМ), при которой аналоговый сигнал кодируется сериями импульсов в дискретном потоке данных. Такая техника модуляции используется в устройствах кодирования-декодирования; д)спектральная модуляция (СМ), при которой волна несущей модулируется по частоте (ЧМ) аналоговым или цифровым сигналом в сочетании с третьим, кодовым, сигналом. Такой способ применяется в военной технике в радиосетях с пакетной коммутацией. "Мусор" - содержащаяся в ЗУ информация которая уже недостоверна, или не нужна. Обычно она появляется в результате уплотнения информации в памяти. Удаление из памяти этой излишней информации известно как "сборка мусора" и, как правило, осуществляется одновременно с уплотнением. Необнаруживаемая ошибка - ошибка, не регистрируемая подсистемой записи/считывания данных. Считается, что причиной этого может быть неадекватность средств контроля ошибок практической реализации этих средств или же несоответствие возникающей ошибки их возможностям. Неопределенность - термин, используемый для обозначения меры информации. Неравенство Крафта . Пусть необходимо сформировать из q-го алфавита однозначно декодируемый код, причем длина i-го кодового слова должна равняться Li . Тогда неравенство Крафта Является необходимым и достаточным условием возможности построеният акого кода, содержащего n кодовых слов. Если в коде отсутствуют свободные кодовые слова, то неравенство переходит в равенство. Носитель - среда для записи данных. Память - устройство или среда, которая может сохранять информацию для последующего ее извлечения. Параметр-1) информация, предоставляемая подпрограмме, процедуре или функции; 2) количественная величина в функции или математической модели, выбираемая или оцениваемая в конкретных обстоятельствах. Поиск информации - извлечение хранимой информации, одна из основных операций, осуществляемых над информацией. Полоса пропускания - диапазон частот с нижним и верхним пределами. Все частоты между этими пределами (но, может быть, и какие-то другие) пропускаются фильтром или каналом с небольшим затуханием. Помеха - любой сигнал, который возникает в электронной или коммуникационной системе и не является передаваемым полезным сигналом (случайное колебание, значение некоторых параметров которого предсказать невозможно) Помехи могут появляться, например, от внешних неблагоприятных воздействий и расстраивать систему, поскольку они могут формировать ложные сигналы, то есть ошибки. Помехоустойчивость - величина интенсивности внешнего воздействия, при которой цифровая схема может работать безошибочно. Логические величины на выходе схемы представляются двумя различными уровнями электрического потенциала. Любая помеха, наведенная в логической схеме внешним воздействием, прибавляется (или вычитается) к передаваемому цифровому логическому сигналу. Запасом по помехоустойчивости является максимальное шумовое напряжение, которое может быть добавлено или вычтено из логического сигнала, и которое не повлияет на пороговое напряжение, необходимое для достижения устойчивого логического состояния. Представление с избытком - смещение (или показатель избытка), которое необходимо прибавить к порядку числа в представлении его с плавающей точкой для получения характеристики числа. Например, порядок, принимающий значения в диапазоне от -128 до +127, представляется 8-разрядной характеристикой с избытком 128, при этом ее значения меняются от0 до 255. Продольный контроль по избыточности - контроль с использованием циклического избыточного кода, как правило, нетривиального,хотя речь может идти и о простом вертикальном контроле, то есть о простом коде с контролем по четности, применяемом, например, вдоль каждой дорожки записи на магнитной ленте. Суть метода контроля с использованием циклического избыточного кода состоит в следующем. С целью обеспечения контроля данных на наличие ошибок, которые могли возникнуть в процессе передачи или при записи (считывании), к каждому блоку добавляются дополнительные цифры. Эти цифры вычисляются на основе содержимого блока на входе, а затем повторно вычисляются приемником или в процессе считывания. Циклический избыточный код - это разновидность полиномиального кода. В принципе, каждый блок можно считать полиномом. Этот полином A умножается в кодере на порождающий полином G, в результате чего формируется полином AG. В процессе передачи или записи этого полинома к нему прибавляется полином ошибки E: AG + E. В декодере эта последовательность делится на тот же самый порождающий полином G. Остаток деления проверяется. Если он отличен от нуля, то регистрируется ошибка и предпринимаются необходимые действия. На практике используются систематические коды, то есть полином A кодируется как Ax + R, где r - степень G, а R - остаток от деления Ax на G. В любом случае не регистрируются только те ошибки, для которых G является делителем E: системотехник выбирает G таким, чтобы свести вероятность этого к минимуму. |