Формы представления информации. Модель системы передачи информации
История возникновения теории кодирования информации. Основные понятия и определения
Создание компьютеров было бы невозможно, если одновременно с их появлением не была бы создана теория кодирования сигналов.
Теория кодирования — одна из тех областей математики, которые заметно повлияли на развитие компьютинга. Ее область действия распространяется на передачу данных по реальным (или зашумленным) каналам, а предметом является обеспечение корректности переданной информации. Иными словами, она изучает, как лучше упаковать данные, чтобы после передачи сигнала из данных можно было надежно и просто выделить полезную информацию. Иногда теорию кодирования путают с шифрованием, но это неверно: криптография решает обратную задачу, ее цель — затруднить получение информации из данных.
Теория кодирования изучает, как лучше упаковать данные, чтобы после передачи сигнала из данных можно было надежно и просто выделить полезную информацию. С необходимостью кодирования данных впервые столкнулись более полутораста лет назад, вскоре после изобретения телеграфа. Каналы были дороги и ненадежны, что сделало актуальной задачу минимизации стоимости и повышения надежности передачи телеграмм. Проблема еще более обострилась в связи с прокладкой трансатлантических кабелей. С 1845 года вошли в употребление специальные кодовые книги; с их помощью телеграфисты вручную выполняли «компрессию» сообщений, заменяя распространенные последовательности слов более короткими кодами. Тогда же для проверки правильности передачи стали использовать контроль четности, метод, который применялся для проверки правильности ввода перфокарт еще и в компьютерах первого и второго поколений. Для этого во вводимую колоду последней вкладывали специально подготовленную карту с контрольной суммой. Если устройство ввода было не слишком надежным (или колода — слишком большой), то могла возникнуть ошибка. Чтобы исправить ее, процедуру ввода повторяли до тех пор, пока подсчитанная контрольная сумма не совпадала с суммой, сохраненной на карте. Мало того, что эта схема неудобна, она к тому же пропускает двойные ошибки. С развитием каналов связи потребовался более эффективный механизм контроля. Первым теоретическое решение проблемы передачи данных по зашумленным каналам предложил Клод Шеннон, основоположник статистической теории информации. Шеннон был звездой своего времени, он входил в академическую элиту США. Будучи аспирантом Ванневара Буша, в 1940 году он получил премию имени Нобеля (не путать с Нобелевской премией!), присуждаемую ученым, не достигшим 30 лет. Работая в Bell Labs, Шеннон написал работу «Математическая теория передачи сообщений» (1948), где показал, что если пропускная способность канала выше энтропии источника сообщений, то сообщение можно закодировать так, что оно будет передано без излишних задержек. Это умозаключение содержится в одной из доказанных Шенноном теорем, ее смысл сводится к тому, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал теоретическую возможность достоверной передачи при наличии шума в канале. Формулу C = W log ((P+N)/N), высеченную на скромном памятнике Шеннону, установленном в его родном городе в штате Мичиган, сравнивают по значению с формулой Альберта Эйнштейна E = mc2. Труды Шеннона дали пищу для множества дальнейших исследований в области теории информации, но практического инженерного приложения они не имели. Переход от теории к практике стал возможен благодаря усилиям Ричарда Хэмминга, коллеги Шеннона по Bell Labs, получившего известность за открытие класса кодов, которые так и стали называть «кодами Хэмминга». Существует легенда, что к изобретению своих кодов Хэмминга подтолкнуло неудобство в работе с перфокартами на релейной счетной машине Bell Model V в середине 40-х годов. Ему давали время для работы на машине в выходные дни, когда не было операторов, и ему самому приходилось возиться с вводом. Как бы то ни было, но Хэмминг предложил коды, способные корректировать ошибки в каналах связи, в том числе и в магистралях передачи данных в компьютерах, прежде всего между процессором и памятью. Коды Хэмминга стали свидетельством того, как можно практически реализовать возможности, на которые указывают теоремы Шеннона. Хэмминг опубликовал свою статью в 1950 году, хотя во внутренних отчетах его теория кодирования датируется 1947 годом. Поэтому некоторые считают, что отцом теории кодирования следует считать Хэмминга, а не Шеннона. Впрочем, в истории техники бесполезно искать первого.
Достоверно только то, что именно Хэмминг первым предложил «коды с исправлением ошибок» (Error-Correcting Code, ECC). Современные модификации этих кодов используются во всех системах хранения данных и для обмена между процессором и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, которые могли бы вызвать царапины и пылинки. Существует множество версий кодов, построенных «по мотивам» Хэмминга, они различаются алгоритмами кодирования и количеством проверочных битов. Особое значение подобные коды приобрели в связи с развитием дальней космической связи с межпланетными станциями, например, существуют коды Рида-Мюллера, где на семь информационных битов приходится 32 контрольных, или на шесть — 26. Среди новейших кодов ECC следует назвать коды LDPC (Low-Density Parity-check Code). Вообще-то они известны лет тридцать, но особый интерес к ним обнаружился именно в последние годы, когда стало развиваться телевидение высокой четкости. Коды LDPC не обладают 100-процентной достоверностью, но вероятность ошибки может быть доведена до желаемой, и при этом с максимальной полнотой используется пропускная способность канала. К ним близки «турбокоды» (Turbo Code), они эффективны при работе с объектами, находящимися в условиях далекого космоса и ограниченной пропускной способности канала. В историю теории кодирования прочно вписано имя Владимира Александровича Котельникова. В 1933 году в «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи» он опубликовал работу «О пропускной способности ?эфира? и ?проволоки?». Имя Котельникова на правах равного входит в название одной из важнейших теорем теории кодирования. Этой теоремой определяются условия, при которых переданный сигнал может быть восстановлен без потери информации. Эту теорему называют по-разному, в том числе «теоремой WKS» (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). В некоторых источниках используют и Nyquist-Shannon sampling theorem, и Whittaker-Shannon sampling theorem, а в отечественных вузовских учебниках чаще всего встречается просто «теорема Котельникова». На самом же деле теорема имеет более долгую историю. Ее первую часть в 1897 году доказал французский математик Эмиль Борель. Свой вклад в 1915 году внес Эдмунд Уиттекер. В 1920 году японец Кинносуки Огура опубликовал поправки к исследованиям Уиттекера, а в 1928 году американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала.
Основные понятия и определения
Рассмотрим основные понятия, связанные с кодированием информации. Для передачи в канал связи сообщения преобразуются в сигналы. Символы, при помощи которых создаются сообщения, образуют первичный алфавит, при этом каждый символ характеризуется вероятностью его появления в сообщении. Каждому сообщению однозначно соответствует сигнал, представляющий определенную последовательность элементарных дискретных символов, называемых кодовыми комбинациями.
Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации.
Код- система соответствия между элементами сообщений и кодовыми комбинациями. Кодер - устройство, осуществляющее кодирование.
Декодер - устройство, осуществляющее обратную операцию, т.е. преобразование кодовой комбинации в сообщение.
Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {xi}, где i = 1, 2,..., m. Количество элементов кода - m называется его основанием. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность символов данного алфавита называется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации - n называется значностью (длиной комбинации). Число различных кодовых комбинаций (N = mn) называется объемом или мощностью кода. Если N0 - число сообщений источника, то N ³ N0. Множество состояний кода должно покрывать множество состояний объекта. Полный равномерный n - значный код с основанием m содержит N = mn кодовых комбинаций. Такой код называется примитивным.
2. Задачи теории информации и кодирования
К теории информации относят результаты решения ряда фундаментальных теоретических вопросов:
- анализ сигналов как средства передачи сообщений, включающий вопросы оценки переносимого ими «количества информации»;
- анализ информационных характеристик источников сообщений и каналов связи и обоснование принципиальной возможности кодирования и декодирования сообщений, обеспечивающих предельно допустимую скорость передачи сообщений по каналу связи, как при отсутствии, так и при наличии помех.
Теория кодирования - раздел теории информации, связанный с задачами кодирования и декодирования сообщений, поступающих к потребителям и посылаемых из источников информации. Эти задачи теория кодирования решает с учетом задачи наилучшего согласования посылаемой информации с каналами связи (каналами передачи данных). Под этим понимается стремление максимально использовать пропускную способность канала, а также обеспечить передаваемым сообщениям нужную степень защищенности от помех.
ЦЕЛИ КОДИРОВАНИЯ: 1) Повышение эффективности передачи данных, за счет достижения максимальной скорости передачи данных. 2) Повышение помехоустойчивости при передаче данных. В соответствии с этими целями теория кодирования развивается в двух основных направлениях: 1. Теория экономичного (эффективного, оптимального) кодирования занимается поиском кодов, позволяющих в каналах без помех повысить эффективность передачи информации за счет устранения избыточности источника и наилучшего согласования скорости передачи данных с пропускной способностью канала связи. 2. Теория помехоустойчивого кодированиязанимается поиском кодов, повышающих достоверность передачи информации в каналах с помехами.
Формы представления информации. Модель системы передачи информации
Различают две формы представления информации — непрерывную и дискретную. Поскольку носителями информации являются сигналы, то в качестве последних могут использоваться физические процессы различной природы. Например, процесс протекания электрического тока в цепи, процесс механического перемещения тела, процесс распространения света и т. д. Информация представляется (отражается) значением одного или нескольких параметров физического процесса (сигнала), либо комбинацией нескольких параметров.
Сигнал называется непрерывным, если его параметр в заданных пределах может принимать любые промежуточные значения. Сигнал называется дискретным, если его параметр в заданных пределах может принимать отдельные фиксированные значения.
Следует различать непрерывность или дискретность сигнала по уровню и во времени.
Наконец, все многообразие окружающей нас информации можно сгруппировать по различным признакам, т. е. классифицировать по видам. Например, в зависимости от области возникновения информацию, отражающую процессы и явления неодушевленной природы, называют элементарной, процессы животного и растительного мира — биологической, человеческого общества — социальной.
По способу передачи и восприятия различают следующие виды информации: визуальную — передаваемую видимыми образами и символами, аудиальную — звуками, тактильную — ощущениями, органолептическую — запахами и вкусом, машинную — выдаваемую и воспринимаемую средствами вычислительной техники, и т. д. ЭВМ как средство обработки информации При рассмотрении ЭВМ как средства обработки информации важную роль играют понятие архитектуры ЭВМ, классификация ЭВМ, структура и принципы функционирования ЭВМ, а также основные характеристики вычислительной техник.
Система передачи информации – совокупность технических средств для передачи информации от источника к приемнику информации.
Для того чтобы представить содержание курса и его основные проблемы рассмотрим блок-схему системы передачи информации, предложенную Шенноном (см. рис. 1).
Рис. Схема системы передачи информации
Для передачи на расстояние сообщение преобразуется в сигнал. Процесс преобразования сообщения в сигнал состоит из трех этапов (операций): преобразование, кодирование, модуляция. В процессе преобразования сообщение, которое может иметь любую физическую природу (изображение, звук и т.д.), преобразуется в первичный сигнал. В телефонии микрофон преобразует звуковые волны (давление) в электрический ток микрофона. В телеметрии датчики преобразуют изменение физических величин (температура, давление и т.д.) в электрические.
Кодирование – преобразование сообщения в сигнал, т.е. отображение сообщений сигналами в виде определенного сочетания элементарных дискретных символов, называемых кодовыми комбинациями (кодовыми словами).
Код – правило, согласно которому каждому сообщению однозначно ставится в соответствие некоторая кодовая комбинация. Кодер – устройство, осуществляющее кодирование.
Кодер источника (КИ) – кодер, использование которого позволяет путем устранения избыточности существенно снизить среднее число символов на букву сообщения (такое кодирование называется оптимальным или эффективным). При отсутствии помех это дает выигрыш во времени передачи или в объеме ЗУ, т.е. повышает эффективность системы передачи данных.
Кодер канала (КК) – позволяет путем внесения избыточности обеспечить достоверность передачи данных при наличии помех (такое кодирование называется помехоустойчивым).
Канал – совокупность средств, предназначенных для передачи сигнала от передатчика к приемнику информации (передатчик, приемник, линия связи и т.д.). Канал связи может быть односторонний (симплексный) и двухсторонний (дуплексный).
Передатчик – служит для преобразования электрического сигнала в сигнал, пригодный для передачи по линии связи.
Модуляцией называетсяизменение параметров переносчика сигнала в соответствии с функцией, отображающей сообщение. Несущим сигналом может быть ток (телеграфия), гармонические низкочастотные или высокочастотные колебания (телефония и т.д.), высокочастотные импульсы (радиорелейная связь и т.д.). Модулируемые параметры называются информативными и могут быть амплитудой, частотой, фазой и т.д. Модулятор – устройство, осуществляющее модуляцию.
При передаче по каналу связи происходит ослабление и искажение передаваемого сигнала, вносимых каналом и действием помех.
Линейные искажения – определяются частотными и временными характеристиками канала. Нелинейные искажения – определяются нелинейностью звеньев канала и видом модуляции.
Линия связи (ЛС) – это среда, используемая для передачи сигнала от передатчика к приемнику. Существуют различные типы линий связи:
Проводные линии связи. Проводные линии связи могут быть воздушными, кабельными, коаксиальными, оптико-волоконными, линиями электропередачи (ЛЭП). Они используются:
– в телефонии – 300–3400 Гц (тональный диапазон);
– в телеграфии – 0–300 Гц (под тональный диапазон);
– в телевидении – 300–3000 мГц;
– ЛЭП – 500–1000 кГц.
Проводные линии связи характеризуются: помехозащищенностью и волновым сопротивлением r= L/C.
При передаче на большие расстояния необходимо использование промежуточных усилительных пунктов (расстояние зависит от используемых частот и типа ЛС).
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|