Кафедра: Автоматика и информационные технологии
ПЕРЕДАЧА ДАННЫХ В ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМАХ. КАНАЛЫ ПЕРЕДАЧИ ДАННЫХ
ВВЕДЕНИЕ
В данной работе приведены упражнения и задачи по большинству разделов дисциплин «Передача данных в информационно-управляющих системах» и «Каналы передачи данных». Предполагается, что, по крайней мере, два обстоятельства могут стимулировать обращение студента к этой работе:
- она раскрывает постановку и характер экзаменационных задач;
- позволяет каждому сформировать достаточно надежную самооценку уровня освоения учебного материала, своевременно сформулировать собственные вопросы к преподавателю.
Для удобства пользователя приведены фрагменты табулированного интеграла вероятностей V(x) (приложение1) и словарик понятий (приложение2), интерпретация которых сама есть предмет научения.
РАЗДЕЛ 1. ДИСКРЕТНЫЙ ИСТОЧНИК ИНФОРМАЦИИ, СТАТИСТИКА ЕГО СОСТОЯНИЙ, КОДИРОВАННЫЙ СИГНАЛ НА ЛОГИЧЕСКОМ УРОВНЕ, РАВНОМЕРНЫЙ И НЕРАВНОМЕРНЫЙ КОД
Упражнение 1.1
Напряжение сети «220 В, 50 Гц» контролируется стрелочным вольтметром на 250 В, шкала которого имеет 100 делений. Через каждые 15 минут показания прибора записываются оператором в журнал.
Охарактеризуйте функциональный состав такой «системы передачи информации». Что именно Вы предлагаете считать источником информации?
2. Аналоговый здесь источник или дискретный?
3. Что есть «среда распространения сигнала» в такой системе?
4. Какова физическая реализация сигнала?
Упражнение 1.2
Напряжение сети «220 В, 50 Гц» контролируется цифровым вольтметром с погрешностью не более сотой доли вольта. Вольтметр, кроме цифрового индикатора, имеет выход на принтер. Оператор смотрит на индикатор от случая к случаю, но через каждые 15 минут показания вольтметра автоматически регистрируются печатающим устройством.
1. Что Вы предлагаете принять за источник информации, за состояние источника?
2. Какова мощность множества состояний источника? Как ее вычислить?
3. Обоснуйте предположения o равномерности / неравномерности распределения вероятностей на ансамбле состояний источника.
Упражнение 1.3
Персонажи детективных романов нередко посылают телеграммы вполне невинного содержания типа «ПРИЕЗЖАЮ В ПЯТНИЦУ» (и отправитель действительно приезжает), а получатель воспринимает это, например, как «УЕЗЖАЙ НЕМЕД-ЛЕННО».
1. Правильно ли думать, что «воcстановление сообщения по сигналу» в любой системе передачи принципиально невозможно без некоторого априорного (до факта передачи) знания у получателя (приемника)?
- если «да», то как Вы определяете сущность, смысл этого знания?
- если «нет, необязательно», то какое же сообщение «отображают» сигналы телеграфа в данном примере?
2. В связи с этим: не правильнее ли говорить «система передачи сигналов» вместо «система передачи информации»?
3. В связи с этим же: правильно ли считать, что
- «сигнальное отображение информации» всегда неоднозначно?
- «сигнальное отображение информации» может быть неоднозначным?
Упражнение 1.4
Вариантом упражнения 1.3 может служить объявление в газете. Например: «ПРОДАЕТСЯ ЗЕРКАЛЬНЫЙ ШКАФ» (по указанному адресу шкаф действительно продается). В отличие от предыдущего, здесь сообщение адресуется произвольно большому числу получателей, среди которых может быть один (или несколько), для кого такой текст тоже может означать «УЕЗЖАЙ НЕМЕДЛЕННО».
Считаете ли Вы, что существуют технические системы передачи информации, в которых разные получатели (технические устройства) различно интерпретируют одни и те же сигналы?
- если «да, существуют», то приведите примеры таких систем.
- если «нет, такие существовать не могут», то обоснуйте свой ответ.
Упражнение 1.5
Некоторый источник информации имеет десять состояний Аi. В таблице приведены вероятности пребывания источника в каждом из состояний Р(Аi).
Распределение вероятностей состояний источника информации
| Ai | A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 |
| P(Ai) | 0.01 | 0.07 | 0.035 | 0.035 | 0.35 | 0.07 | 0.14 | 0.07 | 0.15 | 0.07 |
Используя процедуру Хаффмена или Шеннона - Фано, напишите список слов неравномерного двоичного кода, сопоставив каждому состоянию источника одно слово. Вычислите среднюю длину кодового слова, сопоставьте с длиной слова при равномерном кодировании (подразумевается код с минимальной длиной слова).
Задача 1.6
Напишите список слов равномерного четверичного кода минимальной длины (алфавит {0, 1, 2, 3}), пригодного для отображения, например, двадцати различных команд управления по правилу: <команда управления>:=<кодовое слово>.
Замечания и рекомендации по решению задач РАЗДЕЛА 1
Упражнения 1.1, 1.2 призваны «стимулировать разговор» о таких понятиях теории информации, как «источник информации», «состояние источника», «сообщение о состоянии источника». В этих упражнениях требуется интерпретировать элементы конкретной системы в терминах теории. Интерпретация не обязательно однозначна. В частности, в упражнении 1.1 «источник информации» довольно легко определить различно, так, что он может быть то дискретным, то аналоговым в зависимости от того, как будет определено «состояние источника».
В упражнении 1.2 может показаться, что нет данных для ответа на вопрос 2. На самом деле это не так. В неявном виде такие данные в тексте содержатся. Стоит обратить внимание на погрешность вольтметра.
При ответе на вопрос 3 предполагается, что каждый опирается на свои знания о характере типичного поведения уровня напряжения сети во времени.
В упражнении 1.4 говорится о системе, в которой передача информации осуществляется для многих получателей, в то время как в упражнении 1.3 получатель один. Это замечание делается не для того, чтобы подчеркнуть различие систем, а скорее наоборот, для того, чтобы попытаться сформулировать обобщенные выводы об «априорном знании у получателя», справедливые для систем того и другого типа.
Решение задачи 1.5 предполагает освоение техники построения «оптимального кода» по критерию минимума средней длины слова. Эта техника может быть различной. Лучше познакомиться с той, которая дает так называемый «префиксный код». В связи с решением этой задачи стоит принять во внимание то обстоятельство, что параметры обсуждаемого кода, кроме алфавита кодирования («значности кода») и числа состояний источника, определяются статистической структурой источника. Последнее обстоятельство делает код уникальным, не оптимальным в отношении другого источника, пусть даже имеющего то же число состояний.
РАЗДЕЛ 2. ФИЗИЧЕСКАЯ РЕАЛИЗАЦИЯ ЭЛЕМЕНТАРНОГО СИГНАЛА, МОДУЛЯЦИЯ, СПЕКТРАЛЬНОЕ ПРЕДСТАВЛЕНИЕ ЭЛЕМЕНТАРНОГО СИГНАЛА
Упражнение 2.1
На рис. 2.1 приведен возможный вариант структурной схемы формирователя видеосигналов с ШИМ-манипуляцией для двоичного канала. Символы двоичного алфавита {0,1} на входе формирователя представлены в виде NRZ-сигналов с ТТL-уровнями, как принято в вычислительной технике.
Рис.2.1. Вариант структурной схемы ШИМ – формирователя для двоичного канала
Рис.2.2. Временные диаграммы требуемых выходных ШИМ-сигналов
Предложите варианты подробной функциональной схемы формирователя с аналоговыми или дискретными электронными компонентами, реализующей выходные сигналы в соответствии с рис. 2.2.
Упражнение 2.2
Известно, что применительно к проводным электрическим цепям в качестве носителей сигналов часто используются гармонический или постоянный ток.
Что Вы скажете относительно предложения организовать сигнал на основе шумового переносчика, т.е. случайного процесса? Возможно ли это хотя бы в принципе?
Если «Да, возможно», то поясните, как организовать такие сигналы? Какие параметры модулировать? Каким образом приемник сможет опознавать сигналы?
Если «Нет, невозможно», то также поясните, почему такие сигналы не могут быть реализованы?
Упражнение 2.3
Для ШИМ-сигналов двоичного канала (рис.2.2) и троичного канала (рис.2.3) приведите:
граф-схему алгоритма функционирования опознавателя;
функциональную схему опознавателя, необходимые пояснения, раскрывающие ее работу.
Рис. 2.3. ШИМ – видеосигналы троичного канала
Структурная схема опознавателя показана на рис.2.4. Cостояние цепи Qi = «1», если в данном такте 0 из канала поступил сигнал i = 0, 1, 2. При этом состояния остальных цепей Qj, ji должны быть равны «0».
Рис.2.4. Структурная схема опознавателя элементарных ШИМ – сигналов для троичного канала
Задача 2.4
В двоичном канале символ «0» представлен видеоимпульсом прямоугольной формы длительностью 0,2*10–3с, а символ «1» - импульсом длительностью 0,5*10–3с.
Вычислить необходимую полосу частот канала.
Задача 2.5
В двоичном канале символ «1» представлен радиоимпульсом с прямоугольной формой огибающей длительностью 4*10–2 с. с амплитудой 1,5В, а символу «0» соответствует отсутствие импульса («физический ноль»). Частота несущего колебания составляет 1 кГц. Скорость манипуляции В = 12,5 Бод.
Указать границы частотного диапазона, ограничивающие требуемую полосу частот. Привести в некотором масштабе вид сигнала на оси времени.
Задача 2.6
В троичном канале каждому символу алфавита сопоставлен радиимпульс с прямоугольной формой огибающей длительностью 25*10–3с с модулируемой частотой, которая принимает значения 400, 500, 600 Гц.
Вычислить:
1) требуемую полосу частот канала;
2) привести в некотором масштабе рисунок распределения спектральных плотностей сигналов на частотной оси.
Задача 2.7
В некоторой системе необходимо передавать до 20 различных сообщений. Каждому сообщению сопоставлено слово из букв (элементов) троичного алфавита {0, 1, 2}. Каждая буква отображается ЧМн-радиоимпульсом фиксированной длительности и = 0 со своим значением несущей. Для передачи сигналов используется канал с полосой от 5*103 до 6*103 Гц.
Требуется:
1) привести фрагмент списка кодовых слов, включающий не менее 10 слов.
2) для максимально возможной девиации несущей определить скорость манипуляции, выразив ее в Бодах.
3) привести рисунок типа «осциллограммы» (с обозначением временных параметров) для какой – либо частной реализации кодового слова.
Задача 2.8
В некоторой системе передается до 60 сообщений, каждое из которых представлено словом постоянной длины из букв (элементов) троичного алфавита {0, 1, 2}. Каждая буква отображается ЧМн-радиоимпульсом длительностью 4*10–3с. Девиация частоты составляет 500 Гц на каждый символ алфавита.
1) вычислить минимальную полосу канала для передачи этих сигналов.
2) предложить допустимую нижнюю границу полосы.
Рис. 2.5. Структурная схема опознавателя с компараторами
3) привести фрагмент упорядоченной таблицы кодовых слов (10-15 слов, чтобы понять характер их упорядоченности).
Задача 2.9
В двоичном канале символ «1» отображается прямоугольным видеоимпульсом с амплитудой (на входе опознавателя сигналов) 1В, а символ «0» - нулевым уровнем напряжения. На входе опознавателя присутствует аддитивный шум UШ(t) с нормальным распределением мгновенных значений и среднеквадратичным напряжением Ucк = 15*10–2В.
Структурная схема опознавателя представлена на рис.2.5. Здесь два пороговых (компаратора) устройства, у которых верхний пороговый уровень Uпв=0,6В, а нижний Uпн=0,3В. Правило принятия решений характеризуется следующими выражениями:
Как видно, алгоритм предусматривает возможность «стирания» элементарного сигнала (состояния Q1 = Q2 = «0», t = tотс.).
Допуская одинаковую частость передачи сигналов «0» и «1», определить вероятности неправильного опознавания символов, т.е. вероятности Р0–1, и Р1–0.
Задача 2.10
В двоичном канале физическое отображение сигналов представлено на рис. 2.6.
На входе опознавателя уровень U1=1B, a U2=2B. Кроме того, здесь присутствует аддитивный шум с нормальным распределением значений и среднеквадратичным значением Ucк=0,1В. Опознаватель сигналов представляет собой пороговое устройство (компаратор) с порогом Uп=1,3В. Правило принятия решений характеризуется следующим соотношением
где tотсч - момент взятия отсчета входного процесса в середине тактового интервала (момент стробирования).
Определить вероятности неправильного опознавания сигналов Р0–1 и Р1–0. Как изменятся значения этих вероятностей, если уровень шума уменьшится вдвое?
Задача 2.11
Физическое отображение сигналов в двоичном канале в точке приема представлено на рис.2.7. На входе опознавателя расчетный номинальный уровень Uс= ±1В.
Здесь же присутствует аддитивный шум с нормальным распределением значений и среднеквадратичным значением Ucк=0,28В. Y(t) = Si(t) + Uш(t). Правило принятия решений Qi о значении поступившего сигнала характеризуется следующим соотношением
Рис.2.7. Диаграмма сигналов к задаче 2.11
нятия решений Qi о значении поступившего сигнала характеризуется следующим соотношением
где tотсч - момент взятия отсчета входного процесса Y(t) в середине тактового интервала.
1. Определить вероятности правильного и неправильного опознавания сигналов.
2. Ответить, является ли такой приемник оптимальным в отношении помехоустойчивости? Обосновать ответ.
Упражнение 2.12
На рис.2.8 приведена схема, предназначенная для распознавания элементарных двоичных ШИМ-сигналов S0 и S1 в условиях действия шумов, искажающих их длительность.
В состоянии покоя, когда источник данных не является активным, входная цепь Uвх имеет уровень логической «1» TTL – стандарта. Номинальное физическое представление сигнала S0 – это нулевой уровень напряжения UВХ (пауза) с расчетной длительностью п0=5*10–3с. Сигнал S1 представлен так же, только расчетная длительность п1=10*10–3с.
Микросхема DD1 содержит два ждущих одновибратора типа АГ. Одновибратор DD1.1 имеет расчетную длительность выходного импульса OB1=4*10–3с. Одновибратор DD1.2 - длительность OB2=2*10–3с. Аналогичные одновибраторы выполнены и на элементах DD2.1 (ОВ3=9*10–3с. ) и DD2.2 (ОВ4=2*10–3с ).
Группа элементов DD3.1, DD3.2, DD3.3, DD4.1 предназначена для получения реакции схемы на окончание входного сигнала. Отметим, что здесь необходимо принимать во внимание задержку сигнала в элементах DD3.1, DD3.2, DD3.3.
Задача:
1. Назначив величину тактового интервала О, постройте диаграммы сигналов во входной цепи, а также в выходных цепях одновибраторов, на выходе элемента DD4.1, на выходах всего опознавателя.
2. Вы считаете, что канал, содержащий такой опознаватель элементарных сигналов, надо отнести к категории:
- каналов без стирания элементарного сигнала;
- каналов со стиранием элементарного сигнала;
Обоснуйте свой ответ.
3. Если Вы выбираете ответ «канал со стиранием», то:
- изменением каких параметров схемы можно изменить величину зоны стирания?
Рис.2.8. Функциональная схема опознавателя двоичных ШИМ-сигналов.
- как модернизировать схему, чтобы получить сигнал о происшедшем на данном тактовом интервале стирании?
4. Если Вы выбрали ответ «без стирания», то предложите доработку схемы, которая превращала бы ее в опознаватель со стиранием.
Упражнение 2.13
На рис.2.9 приведена структурная схема преобразователя однополярного двоичного сигнала NRZ в биполярный сигнал «МАНЧЕСТЕР».
Рис.2.9б. Диаграммы входных сигналов преобразователя NRZ – «МАНЧЕСТЕР»
Задача:
1. Для приведенных на рисунке 2.9б входных сигналов постройте соответствующие выходные сигналы, сформулировав правила манчестерского отображения логических символов «0» и «1».
2. Приведите подробную функциональную схему преобразователя.
3. Перечислите показатели, по которым вы считаете необходимым сопоставлять достоинства и недостатки манчестерского сигнала и сигнала NRZ, проведите такое сравнение.
Рекомендации по решению задач РАЗДЕЛА 2
Задачи, рассматриваемые в этом разделе, должны быть отнесены к категории «плохо обусловленных» задач, так как решение почти каждой из них предполагает либо назначение количественного значения какого-либо параметра, либо интерпретацию того или иного понятия. Таковы, например, задачи 2.1, 2.3, 2.8, 2.9. Иначе говоря, решение таких задач предполагает введение элементов проектирования, оно не может быть однозначным.
Целью решения подобных задач является уяснение связей между различными параметрами сигналов, а именно:
- скоростью и широкополосностью (2.4, 2.5, 2.6);
- значностью (основанием) кода и модулируемыми параметрами (2.7, 2.8);
- уровнем шума и помехоустойчивостью (2.9, 2.10, 2.11).
Рассмотрим в качестве типичного примера решение задачи 2.7.
Прежде всего, определим длину троичного кодового слова, исходя из заданного числа передаваемых сообщений NИ=20. Сопоставляя каждому сообщению соответствующее кодовое слово, определим, что понадобится NК=20 слов. Условия задачи предоставляют свободу в отношении выбора типа кода. Если видна какая-либо техническая целесообразность (и мы можем ее обосновать), можно, например, взять кодирование, при котором в каждом кодовом слове на соседних местах не бывает одинаковых элементов алфавита (так называемые «сменно-качественные» коды). Число таких кодовых слов NК связано с параметрами кодового слова соотношением NK=q*(q–1)n–1, в котором q –это значность кода (число элементов алфавита), а n-длина кодового слова. Учитывая, что NKNИ, получим n4 и примем n=4.
Если для кодирования источника информации взять код, у которого в словах фиксированной длины n могут быть использованы любые сочетания элементов алфавита (код «на все сочетания»), то NК=qn и для нашего случая n=3. Этот вариант кодирования также не противоречит условиям задачи.
Напишем фрагмент списка слов. Нередко можно наблюдать попытки написать такой список как случайную последовательность слов. В таком стиле трудно написать и десяток неповторяющихся слов. Следует научиться какому-либо правилу упорядочения слов. В данной задаче не слишком важно, какой именно упорядоченностью воспользоваться. В задаче каждый элемент слова представлен радиоимпульсом со своим значением частоты гармонического колебания fci, i=0, 1, 2. Известно, что при этом практически необходимая часть спектра сигнала определяется шириной главного лепестка спектральной плотности, симметричного относительно значения fci. Обозначим эту полосу fci, i=0, 1, 2. Быть может, следует напомнить, что речь идет о передаче сигнала с двумя боковыми полосами, что используется энергетический критерий широкополосности, а процессы в канале, происходящие в течение данного тактового интервала 0, никак не влияют на процессы в последующих интервалах. Главный лепесток спектра каждого сигнала должен селектироваться своим фильтром.
Обозначим полосу пропускания фильтра fфi, а частоту, соответствующую середине полосы, fф.ср.. Ясно, что полоса fфi должна быть не меньше, чем fci. Если fфi> fci, то в полосу данного фильтра попадает часть главного лепестка спектра «чужого» сигнала. Это эквивалентно помехе при опознавании сигнала. В расчете на идеальные фильтры, т.е. фильтры с идеально крутыми перепадами кривой затухания фi, примем, что полоса fфi= fci, a «несущая» сигнала fci=fф.ср.
Рис. 2.10. Диаграмма распределения частот в канале
Следовательно, всю полосу канала для передачи элементарных сигналов fк, о которой говорится в задаче, придется разбить на три равных участка, а частоты, соответствующие серединам участков, объявить равными fci (см.рис.2.9).
Так мы получим количественные значения fci и fci, а следовательно, и длительность отрезка гармонического колебания И и длительность тактового интервала 0.
При этом мы полагаем, что И=0, т.к. это не противоречит условиям задачи. Допустимо брать И<0 (и это еще один источник неоднозначности решения), но это ведет к уменьшению скорости передачи при заданной широкополосности. В условиях данной задачи нет ничего такого, что мотивировало бы целесообразность такого решения, так как известно, что fcИ= , а для радиоимпульса =2.
Сделаем еще несколько замечаний относительно решения других задач.
В упражнениях 2.1, 2.3 схемы должны содержать те или иные функциональные узлы, генерирующие прямоугольные видеоимпульсы наперед заданной длительности. Чаще всего предлагают узлы на основе двоичного счетчика. Но в условиях этих упражнений нет ничего, что запрещало бы применение и аналоговых элементов, например, одновибраторов. Быть может, следует еще сказать, что конструирование схемы облегчается, если вы начнете с добротного изображения требуемой временной диаграммы.
Для решения задач 2.9, 2.10, 2.11 необходимо обратиться к интегралу вероятностей (см. прил. 1). Методика решения подобных задач рассмотрена, например, в [2].
РАЗДЕЛ 3. КАНАЛ С КОДИРОВАННЫМИ СИГНАЛАМИ. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ, МАТРИЧНОЕ И ПОЛИНОМИАЛЬНОЕ ОПИСАНИЕ ЛИНЕЙНЫХ КОДОВ, ОЦЕНКИ ПОМЕХОУСТОЙЧИВОСТИ
Задача 3.1
Известно, что каноническая форма порождающей матрицы линейного (n,k)-кода имеет следующую структуру: G(n,k) = (I k | Dk, n-k), где I k - единичная матрица размерности k, а D - блок «дополнений» размерности k(n–k), каждая строка которого имеет вес w(D i)≥ d0–1).
По заданной порождающей матрице (15,11)-кода с минимальным расстоянием d0 = 3, приведенной в шестнадцатеричном формате справа, напишите проверочную матрицу H(15,11), с помощью которой составьте список синдромов однократных ошибок в слове.
Напишите проверочную матрицу для укороченного (14,10)-кода.
Задача 3.2
В некоторой системе необходимо передавать до 12 сообщений. С целью обеспечения помехоустойчивости необходимо представить сообщения словами линейного (n, k)-кода, обеспечивающего вероятность безошибочной передачи сообщения (слова) не хуже, чем 0,9995, при том, что сигналы передаются по двоичному симметричному каналу с независимыми ошибками , вероятность происхождения которых Р0–1=Р1–0=РБ=10–4.
Требуется:
1) определить параметры слова избыточного (n, k)-кода;
2) написать порождающую G(n,k) и проверочную H(n,k) матрицы кода (в канонической форме);
3) изложить в графической или текстовой форме алгоритм работы декодера;
4) вычислить вероятности:
- предъявления получателю неискаженного сообщения (слова);
- предъявления получателю сообщения с незамеченными ошибками;
5)определить выигрыш в помехоустойчивости по сравнению с неизбыточным кодом:
- по вероятности получения неискаженного сообщения;
- по вероятности получения сообщения с незамеченными ошибками.
Задача 3.3
Напишите порождающую матрицу линейного (7,4)-кода с минимальным расстоянием d0=3. На ее основе получите матрицу укороченного (5,2)-кода. Напишите полный список кодовых слов, определите минимальное кодовое расстояние.
На основе той же исходной матрицы (7,4)-кода получите порождающую матрицу для расширенного (8,4)-кода с минимальным расстоянием d0 = 4.
Задача 3.4
Первичный преобразователь (датчик) технологического параметра измеряет уровень жидкости в некотором резервуаре. Результат измерения уровня («отсчет») отображается словом неизбыточного двоичного кода на все сочетания. Уровень жидкости меняется в пределах от 0 до 100 мм. Статическая погрешность измерения не превосходит 1мм.
Для передачи сигналов используется двоичный симметричный канал без стирания и памяти. Вероятность ложного опознавания одного бита РБ=5*10–4.
Определите:
1) число состояний источника информации и минимальную длину слова неизбыточного кода;
2) вероятность получения сообщения с незамеченными ошибками («подмена сообщения»);
3) параметры избыточного линейного (n,k) - кода, обеспечивающего вероятность получения сообщения с незамеченными ошибками не хуже 10–6;
4) выигрыш в помехоустойчивости по отношению к неизбыточному коду, оцениваемый по вероятности «подмены сообщения», о которой шла речь в п.2;
5) проигрыш в скорости передачи сигналов по отношению к неизбыточному кодированию («относительную скорость» избыточного (n,k)-кода).
Задача 3.5
Первичный преобразователь технологического параметра представляет каждый отсчет измеряемого параметра (сообщение) трехразрядным десятичным числом в диапазоне от 00,0 до 99,9. Каждая десятичная цифра кодируется, в свою очередь, двоичным кодом с четным весом.
Информация передается по двоичному симметричному каналу без стирания и памяти, у которого вероятность искажения одного бита равна 10–4. Декодер канала декодирует слова с четным весом, обнаруживая ошибки.
Определите:
1) вероятность предъявления получателю безошибочного сообщения;
2) вероятность предъявления получателю ошибочного сообщения из-за незамеченных ошибок в сигнале.
Задача 3.6
Первичный преобразователь, как и в предыдущей задаче, каждое сообщение (отсчет) отображает последовательностью из трех десятичных цифр. Каждая десятичная цифра представлена словом, принадлежащим коду с постоянным весом.
Канал передачи элементарных сигналов - асимметричный, без памяти и стирания. Вероятность ложного опознавания «1» Р1–0=0,5*10–3, а ложного опознавания «0» Р0–1=2*10–3.
Требуется:
1) вычислить минимальную длину кодового слова. Если есть варианты, назначить (выбрать) значение веса слов;
2) вычислить вероятность предъявления получателю неискаженного сообщения;
3) вероятность предъявления получателю сообщения с незамеченными ошибками;
4) вычислить аналогичную вероятность при кодировании десятичной цифры неизбыточным кодом со словами длиной в четыре бита;
5) выигрыш в помехоустойчивости, оцениваемый по вероятности незамеченных ошибок, обеспечиваемый предлагаемым кодом с постоянным весом;
6) проигрыш в скорости передачи сообщений по сравнению с кодированием по п.4).
Упражнение 3.7
Напишите список слов (4,3)-циклического кода, заданного порождающим многочленом g(x) = x+1. Определите минимальное расстояние d0 данного кода.
Требуется:
1) построить на основе регистров сдвига структурную схему декодера, обнаруживающего ошибки в кодовых словах;
2) в рамках ограничений выбранной вами серии ТТЛ-схем построить функциональную схему декодера, включая реализацию ключей, управляющих работой регистров;
3) можно ли предложить циклический код с такой же длиной информационного блока (к=3) и таким же расстоянием d0, но с большей относительной скоростью?
Упражнение 3.8
Охарактеризуйте всевозможные конфигурации векторов ошибок, которые позволяет обнаруживать (7,4)-циклический код, образованный порождающим многочленом g(x) = x3+x+1 и имеющий минимальное расстояние d0=3.
Поясните, какие из перечисленных ошибок могут не обнаруживаться (7,4)-нециклическим кодом с тем же расстоянием. Приведите конкретные примеры таких ошибок.
Упражнение 3.9
На основе регистров сдвига постройте структурную схему декодера с исправлением однократных ошибок для укороченного (15,11)-циклического кода с минимальным расстоянием d0=3 и образующим многочленом g(x) = x4+x+1.
Напишите несколько слов, принадлежащих данному коду. С их помощью проиллюстрируйте поведение декодера в условиях возникновения одно- и двукратных ошибок в кодовых словах.
Нужно ли что–нибудь изменить в схеме декодера с тем, чтобы он декодировал слова укороченного (14,10)-кода?
Рекомендации по решению задач РАЗДЕЛА 3
Задачи 3.1, 3.2, 3.3 преследуют цель дать некоторый тренаж в манипулировании с каноническими формами матриц G(n,k) и H(n,k).
Напомним, что в принципе роль порождающей матрицы G может выполнять любая совокупность из k линейно-независимых векторов длины n, попарные расстояния среди которых не меньше d0. Каноническая форма матрицы предполагает определенную технологию ее формирования. Матрица G представляет собой блочную структуру типа
G(n,k) = (I k | D k, n-k), (3.1)
где I k - единичная матрица размерности k;
D - блок дополнений размерности k*(n–k), каждая строка D i которого имеет вес w(Di)(d0–1).
Проверочная матрица Н по определению ортогональна к G и структурно представляет собой
H(n,k) = ( Dт | I n–k ), (3.2)
где Dт - транспортированный блок D размерности kЧ(n–k);
In–k - единичная матрица размерности n–k.
Следствием ортогональности является
V*HТ = S = 0 (3.3)
- фундаментальное соотношение, лежащее в основе процедуры декодирования по синдрому S линейных (n,k)-кодов. Вектор V принадлежит коду G.
Матричная форма описания линейных кодов позволяет легко получить так называемые «укороченные коды» (задачи 3.1, 3.3). Укороченный (n–z,k–z) - код может быть получен из (n,k) - кода, если в канонической матрице G(n,k) вычеркнуть z строк сверху и z столбцов слева. В отношении помехоустойчивости такой код обладает свойствами неукороченного кода.
В задачах 3.7, 3.8, 3.9 обсуждаются циклические (n,k) - коды, получившие в практике передачи кодированных сигналов наибольшее распространение, благодаря прекрасным свойствам в отношении обнаружения ошибок и удивительно простой схемотехнике декодирующих устройств. В [1], [2 ], [3 ] приведены примеры построения структурных и функциональных схем кодирующих и декодирующих устройств.
В задачах 3.2, 3.4, 3.5, 3.6 требуется вычислять вероятности различных событий, связанных с возникновением в кодовом слове ошибок различных конфигураций. Построение формул для вычисления вероятностей можно освоить, например, с помощью [3]. Для этого только необходимо возобновить в памяти теоремы о сумме и произведении вероятностей для совместного наступления независимых событий, а также всякий раз четко формулировать суть события, вероятность наступления которого вычисляется.
С точки зрения инженерной практики наиболее правдоподобны задачи 3.2 и 3.4. Для данного источника предложить кодирование, помехоустойчивость которого удовлетворяет наперед заданным требованиям. В задаче 3.2 требуется, чтобы вероятность предъявления получателю неискаженной информации РНИ была не менее допустимого значения РНИ.ДОП. Исходим из того, что каждое сообщение отображается одним кодовым словом, а каждое слово передается однократно. Проделаем следующее:
1) закодируем источник неизбыточным кодом, определим k - длину неизбыточного слова;
2) проверим соотношение РНИ.НЕИЗБ = РНИ.ДОП. Скорее всего окажется, что РНИ.НЕИЗБ <Р НИ.ДОП. Если это не так, то неизбыточное кодирование решает задачу;
3) если вероятность предъявления получателю неискаженного сообщения меньше допустимого значения, то мы должны заключить, что понадобится код с исправлением ошибок в слове, так как при неизменном качестве двоичного канала РБ при однократной передаче слова других путей повышения этой вероятности нет;
4) определим максимальную кратность ошибки t, которая должна исправляться. Это легко сделать, если иметь в виду, что в обсуждаемом двоичном канале вероятность возникновения однократной ошибки равна
Cn1*PБ*(1–PБ)n–1; (3.4)
5) знание (или предложение) максимальной кратности исправляемой ошибки дает нам знание максимального расстояния кода, так как необходимо, чтобы d0=2t+1. Имеется в виду, что неравенство имеет минимальную глубину;
6) после этого можно вычислить число контрольных символов в кодовом слове, воспользовавшись известным теоретическим результатом (граница Хэмминга).
2(n–k) Cn0 + Cn1 + ...+ Cnt. (3.5)
Здесь Cni - биномиальный коэффициент.
Убедимся, что с учетом исправления ошибок кратности t и меньше вероятность РНИ.РНИ.ДОП.
Задача 3.4 решается вполне аналогично. Необходимо только иметь в виду, что здесь для уменьшения вероятности предъявления получателю сообщения с незамеченной ошибкой РОШ. мы заинтересованы в повышении кратности r обнаруживаемых ошибок. Исправление ошибок эту вероятность не уменьшит. Для обнаружения ошибок кратности r и меньше понадобится (n,k) - код с расстоянием d0(r+1). Быть может, требованиям задачи удовлетворяет код с расстоянием d0=2 (с четным весом). Если это не так, можно для определения числа контрольных символов (n–k) воспользоваться выражением (3.5).
Наконец, рассмотрим еще решение задачи 3.6, так как она отличается от всех других двумя факторами:
1. Здесь сообщение («отсчет» измеряемой аналоговой величины) отображается не одним кодовым словом, а последовательностью (массивом) из трех слов.
2. Для передачи кодовых слов используется асимметричный двоичный канал, в котором Р1–0 Р0–1.
На рис.3.1 представлены диаграммы сигналов для данного случая. Каждый отсчет измеряемой величины представлен в двоичном канале как последовательность трех десятичных цифр, каждая из которых, в свою очередь, отображается словом кода с постоянным весом, например, кодом «2 из 5». Ниже приведен вариант такого отображения.
0 – 11000 2 – 10010 4 – 01100 6 – 01001 8 – 00101
1 – 10100 3 – 10001 5 – 01010 7 – 00110 9 – 00011
Рис. 3.1. Диаграмма сигналов к задаче 3.6
Требуется вычислить:
РНИ - вероятность предъявления получателю неискаженного отсчета (сообщения).
РОШ - вероятность предъявления отсчета с незамеченной ошибкой.
По-видимому, следует начать с нахождения аналогичных вероятностей для одной декады.
По условию задачи вероятности ложного опознава
1. По теореме о вероятности совместного наступления независимых событий вероятность получения неискаженной декады
РНИ.ДЕК. = (Р1–1)w(P0–0)n-w, (3.6)
где Р1–1, Р0–0 - вероятности правильного опознавания соответственно символов «1» и «0».
2. Видно, что ошибки в кодовом слове не будут замечены, если совместно будет неправильно опознано одинаковое количество символов «1» и «0». Вероятность получения декады с незамеченной ошибкой может быть представлена как
. (3.7)
3. Отсчет имеет смысл неискаженного сообщения, если все три декады не искажены. Вероятность такого события
РНИ. = (РНИ.ДЕК.)3. (3.8)
4. Отсчет не имеет ценности для получателя, если хотя бы в одной декаде содержится незамеченная ошибка
Pош=С3j*P jош.дек.*(Pни дек.)3– j. (3.9)
j=1,2,3
РАЗДЕЛ 4. КОМПЛЕКСНЫЕ ЗАДАЧИ
Задача 4.1
Некоторый технологический параметр (линейное механическое перемещение) может изменяться в пределах от 0 до 200мм. Необходимо передавать сообщения о перемещении с погрешностью не более 1мм. Для передачи сообщений выделяется один канал аппаратуры частотного уплотнения (симметричный без стирания и памяти) с вероятностью ложного опознавания буквы, равной 2*10–5 и полосой 140 Гц.
Предложить линейный (n,k) - код, обеспечивающий вероятность предъявления получателю сообщения с незамеченной ошибкой РОШ не хуже, чем 10–10. Написать порождающую матрицу кода. Определить время, необходимое для передачи одного кодового слова (сообщения).
Задача 4.2
Некоторый технологический параметр (линейное механическое перемещение) может изменяться в пределах от 0 до 200 мм. Необходимо передавать сообщения о перемещении с погрешностью не более 1 мм. Для передачи используется модулятор, отображающий логическую «1» кодового слова отрезком гармонического колебания длительностью 2*10–3с частоты 10 кГц, а логический «0» - длительностью 4*10–3с той же частоты. Канал передачи бит - симметричный без стирания и памяти с вероятностью неправильного опознавания бита, равной 10–4.
Предложить линейный (n,k) - код, обеспечивающий вероятность предъявления получателю сообщения с незамеченной ошибкой РОШ не хуже, чем 2*10–6. Написать порождающую матрицу кода. Определить требуемый частотный диапазон канала, попытаться указать его границы, время передачи одного кодового слова.
Задача 4.3
В некотором резервуаре уровень жидкости может изменяться в пределах от 0 до 2м. Необходимо передавать сообщения об уровне с погрешностью не более 5 мм. Каждое сообщение кодируется двоичным словом с постоянным весом. Двоичный канал асимметричный. Логическая «1» отображается видеоимпульсом амплитудой 2В и длительностью 5*10–3с, а логический «0» - видеоимпульсом той же амплитуды и длительностью 2*10–3с. Вероятность ложного опознавания «1» Р1–0 = 0,5*10-4, а ложного опознавания «0» Р0–1 = 2*10-4.
Предложить код, эффективный в асимметричных каналах. Вычислить необходимые параметры кодового слова, вероятности предъявления получателю правильного сообщения (слова), сообщения с независимыми ошибками.
Задача 4.4
Первичный преобразователь технологического параметра каждый отсчет представляет трехразрядным десятичным числом в диапазоне 00,0 - 99,9. Каждая десятичная цифра, в свою очередь, кодируется двоичным кодом с четным весом.
Информация передается по двоичному симметричному каналу без стирания и памяти, у которого вероятность искажения одного бита равна 10–5. Декодер обнаруживает ошибки в словах кода с четным весом.
Определить вероятности предъявления получателю правильного сообщения, сообщения с незамеченными ошибками, привести функциональную схему декодера, пояснить ее работу.
Замечания к задачам РАЗДЕЛА 4
Задачи, названные комплексными, мало чем отличаются от задач предшествующих разделов. Пожалуй, единственное, что их отличает - это некоторая конкретизация источника данных и «связывание» воедино вопросов, которые до этого обсуждались порознь.
Если иметь в виду не характер, а конкретное содержание задач 4.1 - 4.4, то можно указать на основной источник ошибок при их решении. Как правило, это неумение корректно определить число состояний источника данных по заданной допустимой погрешности измерения. Число состояний источника влияет на значения параметров кода, и если оно вычислено неправильно, то решение задачи, естественно, оказывается испорченным, если даже все последующие этапы логически верны.
ПРИЛОЖЕНИЕ 1Значения интеграла вероятностей V(x)
Значения интеграла вероятностей Таблица П.1.1
| x | 0 | 1 | 2 | 3 | 4 |
| 0 | 5,00*10–1 | 4,60*10–1 | 4,21*10–1 | 3,82*10–1 | 3,45*10–1 |
| 1 | 1,59*10–1 | 1,36*10–1 | 1,15*10–1 | 9,68*10–2 | 8,08*10–2 |
| 2 | 2,27*10–2 | 1,79*10–2 | 1,39*10–2 | 1,07*10–2 | 8,20*10–3 |
| 3 | 1,35*10–3 | 9,68*10–4 | 6,87*10–4 | 4,83*10–4 | 3,37*10–4 |
| 4 | 3,17*10–5 | 2,07*10–5 | 1,34*10–5 | 8,54*10–6 | 5,41*10–6 |
| 5 | 2,87*10–7 | 1,70*10–7 | 9,96*10–8 | 5,79*10–8 | 3,33*10–8 |
| 6 | 9,87*10–10 | 5,30*10–10 | 2,82*10–10 | 1,49*10–10 | 7,77*10–11 |
| 7 | 1,28*10–12 | 6,24*10–13 | 4,01*10–13 | 1,44*10–13 | 6,81*10–14 |
| x | 5 | 6 | 7 | 8 | 9 |
| 0 | 3,08*10–1 | 2,74*10–1 | 2,42*10–1 | 2,12*10–1 | 1,84*10–1 |
| 1 | 6,68*10–2 | 5,48*10–2 | 4,46*10–2 | 3,59*10–2 | 2,87*10–2 |
| 2 | 6,21*10–3 | 4,66*10–3 | 3,47*10–3 | 2,55*10–3 | 1,87*10–3 |
| 3 | 2,33*10–4 | 1,59*10–4 | 1,08*10–4 | 7,23*10–5 | 4,81*10–5 |
| 4 | 3,40*10–6 | 2,11*10–6 | 1,30*10–6 | 7,93*10–7 | 4,79*10–7 |
| 5 | 1,90*10–8 | 1,07*10–8 | 5,99*10–9 | 3,32*10–9 | 1,82*10–9 |
| 6 | 4,02*10–11 | 2,05*10–11 | 1,04*10–11 | 5,23*10–12 | 2,60*10–12 |
| 7 | 3,19*10–14 | 1,48*10–14 | 6,80*10–15 | 3,09*10–15 | 1,39*10–15 |
Столбец х - целые значения аргумента.
Строка х - десятые доли значений аргумента.
ПРИЛОЖЕНИЕ 2
СЛОВАРЬ ТЕРМИНОВ ОСНОВНЫХ ПОНЯТИЙ, ЗАТРАГИВАЕМЫХ В УПРАЖНЕНИЯХ И ЗАДАЧАХ
Алфавит
1. В лингвистике: совокупность букв, слоговых знаков и других графем данной системы письма, расположенных в определенном порядке [4].
2. В кодировании: конечное счетное множество символов {0, 1, 2, . . . , (q-1)}, используемых для образования сигналов. Такой алфавит принято называть двоичным, троичным, в общем случае - q-ичным. Здесь 0, 1, 2, ... - это необязательно цифры. Символы алфавита рассматриваются как неделимые, если даже (в некоторых случаях) они структурно разложимы на какие-либо составляющие.
Число символов (букв) алфавита иногда называют значностью алфавита.
Сигнал
1. Знак (от латинского signum). Физический процесс (или явление), несущий сообщение (информацию) о каком-либо событии, состоянии объекта наблюдения, либо передающий команды управления, указания, оповещения, и т.д. [4].
2. Физическое отображение сообщения (информации). Физическую основу сигнала составляет какой-либо процесс, переносящий энергию в рассматриваемой среде и называемый носителем сообщения. Носитель становится сигналом в процессе модуляции. Параметры носителя, изменяемые во времени в соответствии с передаваемым сообщением, называют информативными [1].
Когда не конкретизирована физическая реализация символа (элемента) алфавита, говорят о логическом (абстрактном) сигнале. Физическую реализацию какого-либо символа алфавита называют элементарным физическим сигналом.
Видеосигнал (видеоимпульс)
Элементарный сигнал, носителем которого является постоянный ток.
Радиосигнал (радиоимпульс)
Элементарный сигнал, носителем которого является гармонический ток. Радиоимпульс как функция времени имеет вид отрезка гармоники, «огибающая» которой может изменяться по различному закону, в том числе - оставаться неизменной. Термин радиоимпульс не связывают с конкретным значением частоты колебания носителя.
Модуляция1. Размеренное, закономерное изменение, перемена состояния (От латинского modulatio - мерность, размеренность) [4].
2. Непрерывное («гладкое») изменение во времени одного или нескольких параметров носителя в соответствии с передаваемым сообщением.
МанипуляцияСкачкообразное изменение параметра носителя. Часто используемые обозначения:
ЧМн - частотная манипуляция;
ШИМ, ШИМн - широтно-импульсная манипуляция;
ФИМн (ФМн) - фазоимпульсная манипуляция. ОФМн – относительная фазоимпульсная манипуляция;
АИМн - амплитудно-импульсная манипуляция.
Термины «модуляция» и «манипуляция» не всегда строго разделяются. Нередко термин «модуляция» покрывает то и другое понятие.
Девиация частотыРазность значений частот носителя, каждое из которых сопоставляется символу алфавита, отображаемому в физической области частотно-манипулированными сигналами.
Канал
1. Совокупность технических (и программных) средств и среды распространения сигналов, обеспечивающих генерирование, передачу и опознавание сигналов, отображающих сообщения в соответствии с принятым кодом и модуляцией.
2. Полоса частот, время передачи или иной физический ресурс, выделяемый в данной системе передачи определенных сообщений [4]. В связи с этим говорят о частотных или временных каналах.
q-ичный канал
Канал, входной алфавит которого содержит q символов. В связи с этим как о частном случае говорят о двоичном канале, если алфавит передаваемых символов {0, 1} является двоичным, безотносительно к их физической реализации. Можно говорить и о кодовом канале, если в качестве входного алфавита рассматривать конечное множество слов некоторого кода.
Канал без стирания (сигнала)
Канал, в котором выходной алфавит (множество решений о значении сигнала) совпадает с входным.
В частности, применительно к двоичному каналу опознаватель сигналов на каждом такте следования элементарных сигналов непременно отождествляет их (быть может и ошибочно) с «0» или «1».
Канал со стиранием (сигнала)
Канал, в котором выходной алфавит содержит (по отношению к входному) дополнительный, «пустой» символ. Например, опознаватель сигналов двоичного канала со стиранием на некоторых тактах 0 под влиянием помех не может отнести принимаемый символ ни к «0», ни к «1», относит его к «пустому», «стирает».
Если входным алфавитом канала считать множество кодовых слов, то уместно говорить о стирании в канале с кодированными сигналами. «Стирание» кодового слова может быть обеспечено декодером, обнаруживающим ошибки в словах.
Симметричный двоичный каналКанал, в котором вероятности ложного опознавания символов Р0–1, и Р1–0 одинаковы по величине. В противном случае канал называется асимметричным.
Канал с независимыми (некоррелированными) ошибками
Канал, в котором вероятность ошибки в опознавании символа на данном такте не зависит от наличия ошибок на предшествующем. Наличие/отсутствие ошибки на данном такте не влияет на вероятность аналогичного события на последующем.
Для двоичного канала это означает, что вероятности Р0–1 = Сonst1; Р1–0 = Сonst2, т.е. не зависят от времени, порядка следования символов в кодовом слове.
Код
1. В широком смысле - соглашение между отправителем и получателем сообщений о правилах формирования и интерпретации сигналов.
2. В узком смысле - совокупность символов алфавита и система определенных правил, при помощи которых информация может быть представлена (закодирована) в виде набора из таких символов для передачи, обработки и хранения. Конечная последовательность символов называется кодовым словом [4].
Равномерный код
Код, все слова которого имеют одинаковую длину. В противном случае код называется неравномерным.
Префиксный код
Неравномерный код, у которого ни одно кодовое слово не является началом другого, более длинного слова. Это позволяет приемнику однозначно опознавать слова в поступающей последовательности бит (элементарных сигналов) без каких-либо дополнительных разделителей между словами.
Кодовый вектор
Одна из возможных математических интерпретаций кодового слова, при которой каждый элемент слова рассматривается как независимая координата, принимающая значения из конечного дискретного множества, называемого алфавитом. Двоичный вектор образует двоичные векторы. Слово длины n интерпретируется как n - мерный вектор.
Вес двоичного вектора w(Vi)
Это число единиц, содержащихся в векторе. Здесь Vi – это вектор, принадлежащий коду.
Двоичный вектор ошибки Еj
Вектор, расположение единиц в котором соответствует расположению искаженных элементов в векторе Fi. Математическая модель происхождения ошибок Fi=Vi Ej, где - знак суммирования по mod2, Vi - неискаженный вектор.
Расстояние (Хэмминга) между двумя двоичными векторами
1) минимальное число ребер геометрической модели векторного пространства, соединяющих данные векторы;
2) вес суммы по mod2 рассматриваемых векторов di,j = w(A i A j).
Минимальное расстояние двоичного кода d0
Минимальное значение из всех попарных расстояний между векторами кода.
Неизбыточный двоичный код (на все сочетания)
Код с минимальным расстоянием d0 = 1.
Избыточный двоичный код
Код с расстоянием d0 2.
Разделимый избыточный код
Код, в кодовых словах которого фиксированы позиции, занимаемые информационными (неизбыточными) и контрольными (избыточными) символами. В противном случае избыточный код называется неразделимым, например, код с постоянным весом слов (на одно сочетание).
Систематический разделимый код
Код, в словах которого все контрольные символы расположены компактной группой (обычно в конце слова).
Относительная скорость R избыточного (n,k)-кода
Показатель снижения скорости передачи сообщений относительно неизбыточного кода R=k/n.
Синдром
1). (Медицина). Закономерное сочетание симптомов, обусловленное единым патогенезом [4] (от греческого syndrome - скопление).
2). (Кодирование). Вектор S = Fi*HТ= Е j*НТ длины (n-k), рассматриваемый как признак наличия ошибок в кодовом слове.
Здесь Fi - декодируемое слово (n,k)-кода;
НТ - транспонированная проверочная матрица;
E j - вектор ошибок, который «породил» данный синдром.
Декодирование по синдрому1. Декодирование с обнаружением ошибок (без попытки исправлять) - отнесение принятого слова (n,k)-кода к категории «разрешенных», отображающих сообщения, если синдром S=0, предъявление слова получателю. Отнесение к категории «запрещенных», если S≠0, «стирание» принятого слова.
2. Декодирование с исправлением ошибок - вычисление (или выборка из памяти) вектора ошибки Е j по найденному синдрому. Предъявление получателю слова Q i = Fi E j, где Fi принятое из канала слово (n,k)-кода. Не исключается Е = 0. Тогда Q i = Fi = Vi.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Дмитриев В.И. Прикладная теория информации: Учебник для студентов вузов по спец. «Автоматизированные системы обработки информации и управления». М.: Высшая школа, 1989. 320 с.
2. Гойхман Э.Ш., Лосев Ю.И. Передача информации в АСУ. М.:Связь, 1976. 280 с.
3. Аршинов М.Н., Садовский Л.Е. Коды и математика. М.:Наука, Главная редакция физико-математической литературы, 1983. 144 с.
4. Энциклопедический словарь / Гл. ред. А.М. Прохоров. 3-е изд. М.:Сов. энциклопедия, 1984. 1600 с.