информатика. Документ Microsoft Word555. Задание Составьте словарь терминов по теме. Алгоритм
 Скачать 111.02 Kb.
|
|
Пропускная способность канала - скорость передачи информации любым, сколь угодно зашумленным каналом, которая никогда не может быть превышена без ошибки, но, в принципе, достижима с некоторой произвольно малой вероятностью ошибки. Эта теорема была впервые сформулирована и доказана К.Э. Шенноном в 1948 г. Он показал, что всегда существует некоторый код с исправлением ошибок, с помощью которого можно снизить вероятность ошибки до любого заранее установленного уровня. Среди результатов, полученных Шенноном для конкретных каналов, наиболее известным является результат, полученный для ограниченного по мощности непрерывного канала, в котором присутствует белый гауссов шум. Если мощность канала ограничена величиной Ps , а мощность шума - величиной Pn , то пропускная способность (бит/с) такого канала выражается формулой C = 1/2v log (1 + Ps / Pn ). Если это дискретный во времени канал, то v - число периодов дискретизации в секунду, а если это непрерывный во времени канал, то v - минимальное число отсчетов в секунду, необходимое для извлечения из канала всей информации. Протокол передачи данных - набор правил и соглашений, определяющих форматы данных и процедуры передачи для обмена информацией между взаимодействующими процессами, функциональными или логическими модулями, абонентскими станциями и т.д. Распаковка - процесс преобразования информации из упакованного формата в форму, при которой можно получить непосредственный доступ к отдельным элементам данных. Расстояние Хемминга - d( 2u, v 0) между двумя словами u и v одинаковой длины равно числу несовпадающих разрядов этих слов. Оно используется в теории блочных кодов, предназначенных для обнаружения и справления ошибок. Если длина слов u и v конечна, то расстояние Хемминга между этими словами также конечно, поскольку d(u, v) <= n. Эту меру можно называть расстоянием, так как она неотрицательна, нульрефлексивна, симметрична и удовлетворяет неравенству треугольника 0 <= d(u, v); d(u,v) = 0, если и только если u = v ; d(u,v) = d(v,u); d(u,w) <= d(u,v) + d(v,w). Расстояние Хемминга играет важную роль в теории кодов с обнаружением ошибок и кодов с исправлением ошибок. Расширение источника - процесс одновременного кодирования группы символов или результаты этого процесса. Если символы q-ичного источника информации группируются в блоки длиной r и эти блоки обрабатываются (например, кодируются) подобно символам из алфавита объемом q , то подобный составной источник называется r-расширением исходного источника. Свертка - в математике операция объединения двух функций w и f, в результате которой получается третья функция g, такая, что или соответствующая непрерывная операция). Эту операцию можно рассматривать как преобразование входной функции f в выходную функцию g путем наблюдения первой через окно w фиксированного размера. В теории кодирования f - это сигнал, а g -отклики на него линейного канала; тогда g - это результат действия на данный сигнал (рассматриваемый как последовательность элементов) временной характеристики линейного канала. Временная характеристика канала представляет собой последовательность элементов формируемую на выходе канала при подаче на его вход сигнала, один элемент которого имеет амплитуду, равную единице, а все остальные элементы - нули. В этом случае говорят, что производится свертка входной сигнальной последовательности и временной характеристики канала. Обратный процесс называется деконволюцией: для восстановления входной сигнальной последовательности над выходной, которая была подвергнута свертке, и последовательностью, которая представляет временную характеристику канала, выполняется операция деконволюции. Важно (как с математической, так и с практической точки зрения), чтобы свертка дискретных сигналов соответствовала обычному умножению многочленов. Сверточный код - линейный код с исправлением ошибок, характеризующийся порождающей матрицей размера k x n G = (g [x]), ij элементы которой g [x] являются многочленами; наивысшая ij степень многочлена m называется памятью кода. Величина c = m +1 называется предельной длиной кода. Линейные блочные коды можно рассматривать как специальный случай сверточных кодов с m = 0 и c = 1. Сверточные коды часто задаются параметрами (n, k) или (n,k,c), хотя, когда говорят "n,k-код", обычно подразумевают блочный код, а не сверточный. Сеть - структура с многочисленными связями, состоящая из набора ячеек различных размеров, связанных между собой стрелками и соединенных по заданному условию в ориентированный граф, который может содержать циклы. Сеть связи - система, включающая несколько источников информации и (или) несколько пунктов назначения, посредством которой источник информации может достаточно эффективно и надежно передавать эту информацию в пункт назначения. Сжатие данных - любой из многих методов в теории информации, с помощью которого производится кодирование данных с целью сокращения их избыточности. Аналогичные методы используются при регистрации информации. Методы сжатия могут уменьшать объем буквенного текста. По существу, сжатие данных - это кодирование источника. Сигнал - форма представления данных, при которой данные рассматриваются в виде последовательности значений скалярной величины- амплитуды, записанной (т.е. измеренной, напечатанной или нарисованной) во времени. Чаще всего, но не всегда, амплитудой является электрический потенциал. В информационных системах под сигналом понимают физический процесс, отображающий (несущий) сообщение. Символ - наименьшая единица информации в записи. Скорость создания сообщения - так в американской литературе при заданной точности сообщения называют эпсилон-энтропию (см. энтропия сообщения). Скорость передачи информации - скорость, с которой от устройства или через схему может передаваться информация. Единица измерения этой скорости обычно указывает количество информации, передаваемое за один цикл, например, число знаков в секунду и бит в секунду. В схемах передачи данных иногда используется такая единица скорости передачи, как бод. Словарь - любая структура данных, представляющая собой множество элементов, для которого определены такие операции, как вставка и удаление, а также проверка на принадлежность. Сложность - "трудность" решения вычислительных проблем, измеренная в терминах некоторого ресурса, потребляемого в процессе вычисления. Ресурс может быть абстрактным или конкретным, с пространственными или временными характеристиками. Анализ сложности вычислительных проблем в настоящее время является областью очень активных исследований и имеет важные практические применения. Существуют следующие виды сложности: сложность систем, сложность вычислений, сложность кодирования, Сложность систем - выделяются два общих принципа оценки сложности; они применимы к системам любого типа. Согласно первому принципу сложность системы должна быть пропорциональна объему информации, необходимой для описания этой системы. В данном случае слово " информация" понимается чисто синтаксически, а не семантически и не прагматически. Одним из способов описания такой дескриптивной сложности является оценка числа элементов, входящих в систему (переменных, состояний, компонентов), и разнообразия взаимозависимостей между ними. В соответствии со вторым общим принципом сложность систем должна быть пропорциональна объему информации, необходимому для разрешения любой нечеткости, связанной с рассматриваемой нечеткостью. И в данном случае рассматривается синтаксическая информация, однако эта информация основывается на соответствующей мере нечеткости. Сложность колмогоровская - минимальное число двоичных знаков, содержащих всю необходимую информацию для идентификации объекта. Случайная выборка - выбор элементов для изучения таким образом, чтобы измерения, проведенные на элементах выборки, дали информацию об аналогичных элементах, не вошедших в выборку, причем вероятность включения в выборку каждого элемента одинакова. Элементы могут отбираться с помощью таблиц случайных чисел или же с помощью механических манипуляций, например, с картами или монетами. Случайная последовательность - последовательность символов с псевдослучайными свойствами, предназначенная для моделирования помех. Сокращение избыточности - уменьшение объема буквенного текста за счет использования одного из методов кодирования (сжатие данных). Сообщение - порция информации передаваемой в системе с коммутацией сообщений. Сообщение может быть произвольной длины (от нескольких битов до целого файла), но никакая часть сообщения не может быть передана конечному адресату, пока оно не будет принято целиком в узле сети, смежном с пунктом назначения. Различаются дискретные и непрерывные сообщения. Дискретные сообщения формируются в результате последовательной выдачи источником отдельных элементов - знаков. Разновидностью дискретных сообщений являются данные. Непрерывные сообщения неразделимы на элементы.Они описываются функциями времени, принимающими непрерывное множество значений. Примерами могут служить речь, телевизионное изображение. Сортировка - процесс переупорядочивания информации по возрастанию или убыванию значений ключей сортировки. Спектральная модуляция - один из основных типов модуляции, при котором волна несущей модулируется по частоте аналоговым или цифровым сигналом в сочетании с третьим, кодовым, сигналом. Такой способ применяется в военной технике в радиосетях с пакетной коммутацией. Стандарт на шифрование данных - алгоритм, используемый в США для шифрования сообщений. Стартстопная передача - асинхронная передача, при которой каждой группе кодовых элементов, соответствующих сигналу символа, предшествует сигнал начала, подготавливающий приемное устройство к приему. Завершает передачу группы сигнал окончания, устанавивающий приемное устройство в состояние покоя. Стационарный источник - источник со стационарной мерой, т.е. вероятностной мерой (не зависящей от сдвига по времени). Теорема о кодировании источника - в теории связи: утверждение о том, что выходной поток информации из любого источника, имеющий энтропию в H единиц на один символ, может быть закодирован с помощью алфавита из N символов таким образом, что символы потока из источника информации будут представлены кодовыми словами, средневзвешенная длина которых не меньше, чем H/log N, (где основание логарифма согласуется с единицами измерения энтропии). Кроме того, теорема утверждает, что этому нижнему пределу можно подойти сколь угодно близко при работе с любым источником, для чего нужно выбрать соответствующий неравномерный код и и пользовать достаточно длинное расширение источника. Теорема была впервые сформулирована и доказана К.Э.Шенноном в 1948 г. Упаковка - способ компактного хранения (данных) с целью сокращения объема памяти для размещения одного и того же объема данных.Существует несколько путей достижения компактности, например, хранение нескольких байтов в одном слове или замена повторяющегося символа или слова триплетом, включающим: специальный код, определяющий начало триплета; один из элементов заменяемого символа или слова; число повторений символа или слова. Уплотнение байт - вид временного уплотнения, при котором полный байт одного подканала передается как единое целое и байты из различных подканалов размещаются друг за другом во временных окнах. Уплотнение памяти - один из способов перемещения блоков информации в оперативной памяти с целью расширения свободных областей. Фазовая модуляция - один из основных типов модуляции, при которой изменяется фаза волны несущей. Этот способ модуляции часто используется в сочетании с амплитудной модуляцией в высокоскоростных модемах. Файл - информация, хранимая во вспомогательном ЗУ (то есть обычно на магнитном диске или магнитной ленте) с целью ее сохранения после завершения отдельного задания (а) или преодоления ограничений, связанных с объемом основного ЗУ (б). В файле могут содержаться данные, программы, тексты и любая другая информация. Факсимиле - фототелеграф, устройство для передачи изображений. Изображение разворачивается в передатчике, восстанавливается в приемнике и переносится на определенные сорта бумаги. Фильтр - простая электрическая схема или несколько более сложное устройство, осуществляющее процесс фильтрации. Фильтрация - обработка сигнала (в простой электрической цепи или в несколько более сложном устройстве), приводящая к изменению как формы сигнала во временной области так и образа сигнала в частотной области. При фильтрации во временной области каждый элемент исходного сигнала заменяется последовательностью элементов, пропорциональных ему по амплитуде, но сдвинутых по времени; сумма (в случае линейной фильтрации) этих элементов образует новый сигнал. При фильтрации в преобразованной области элементами исходного сигнала будут не его смещенные во времени копии, а компоненты его преобразования Фурье или Уолша, соответствующие различным частотам или секвентам. Используется также ряд других преобразований. Как во временной области, так и в различных преобразованных областях фильтрация играет весьма важную роль при уплотнении. Простой, но весьма типичный пример фильтрации в частотной (Фурье-) области связан с использованием резонансных цепей, реализующих фильтры нижних частот, полосовые фильтры, фильтры верхних частот и режекторные фильтры. Такие фильтры широко используются в каналах передачи данных и в модемах. Формальный язык - конечное или бесконечное подмножество множества всех слов, образованных из некоторого конечного набора символов. Множество называется алфавитом языка. Указанное подмножество множества называют 1 языком над алфавитом 0 или -языком. Таким образом, в теории формальных языков под языком понимается просто совокупность строк без всякой связи с их возможной семантикой. Несмотря на существенную роль, которую играют бесконечные языки, их исследование ограничено классом рекурсивно перечислимых языков. Цифровая обработка сигналов - группа методов обработки сигналов, для которой характерно преобразование сигналов цифровыми способами. Преимущества цифровых методов по сравнению с аналоговыми состоят в упрощении работы с памятью (например, последовательности отсчетов можно воспроизводить при разных скоростях и в разных направлениях), а также в расширении набора используемых арифметических операций и в повышении допустимой сложности алгоритмов. Однако их основное достоинство состоит в возможности беспредельного увеличения точности вычислений. Главный недостаток цифровых методов заключается в том, что для некоторых специфических приложений они оказываются более медленными, чем аналоговые методы. К настоящему времени разработан целый ряд специализированных цифровых устройств, имеющих при сохранении всех названных преимуществ достаточно высокое быстродействие, что достигается, однако, ценой потери гибкости. Цифровая передача данных - для представления цифровых данных при их передаче используются дискретные сигналы, принимающие конечное множество значений. В системах с гальванической связью для представления дискретных величин (обычно 0 и 1) используются различающиеся значения напряжения (или тока). Цифровой передаче данных свойственны весьма низкие значения коэффициента ошибок и довольно высокие скорости. Слабые сигналы можно регенерировать, сохраняя при этом суммарную вероятность ошибки на довольно низком уровне. Поскольку при цифровой передаче используются только логические нули и единицы, сигналы от нескольких источников легко уплотнять цифровыми методами. Цифровые данные можно передавать и по линиям переменного тока. Такие линии не пропускают постоянную составляющую сигнала, поэтому здесь используется иной метод передачи. По линиям переменного тока данные передаются при помощи аналоговых сигналов. Цифровые сигналы преобразуются в аналоговую форму при помощи устройства, называемого модулятором. Цифровая сортировка - алгоритм сортировки, при котором файл сначала сортируется по цифре в младшем разряде ключа сортировки, затем по следующей значащей цифре и т.д. Завершается сортировка проходом по цифре в старшем разряде ключа сортировки. Данный алгоритм лучше всего реализуется с использованием связных списков. Цифровая фильтрация - фильтрация сигналов на основе методов их цифровой обработки. Цифровой сигнал - сигнал,значение напряжения которого в любой момент времени совпадает с одним из нескольких (обычно двух) уровней. Двухуровневый сигнал иногда называют двоичным цифровым сигналом или просто двоичным сигналом. В двоичных логических схемах, работающих с двумя дискретными уровнями напряжения, один из уровней (обычно высокий) соответствует логической "1" (истина), а другой - логическому "0" (ложь). |