Лекция 1. Сигнал, информация и сообщение.

Введение

Большинство изданий по дисциплине теории информации написано на высоком математическом уровне. В то же время теория информации – наука прикладная, она служит теоретическим фундаментом техники связи, радиолокации, техники обработки информации. Её результаты должны находить практическое применение. Для этого нужно чтобы инженеры – проектировщики систем могли понять и оценить результаты теории.

^{Информационная наука находит применение в самых разнообразных областях. В связи с этим нет всеобщего для всех наук классического определения понятия “информация”. В каждом направлении используют определение ее отдельных составляющих, наиболее важных для данной науки. Для теории систем, информация выступает как мера организации системы. Для теории познания важно, что информация изменяет наши знания. Под информацией понимают не все получаемые сведения, а только те, которые еще не известны и являются новыми для получателя. В этом случае информация является мерой устранения неопределенности. Для машинной обработки информация должна быть представлена в виде сообщений на определенном языке. Специалистам связи важно, что информация - это сведение, являющиеся объектом передачи и обработки.}

^{Приступая к систематическому изучению теории информации,} следует по возможности уточнить смысл понятий «сигнал» и «сообщение».

Сигнал ( лат.Signum-знак)- процесс изменения во времени физического состояния какого-либо объекта, служащий для отображения регистраций или передачи SMS.

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

Канал электросвязи – это совокупность технических средств и среды распространения сигналов, обеспечивающая при подключении абонентских устройств передачу сообщений от источника к получателю.

Рисунок 1.1 - Обобщенная структурная схема канал связи

Введение способа измерения количества информации К. Шенноном в конце 40-х годов привело к формированию самостоятельного научного направления под названием “Теория информации”. Параллельно на основе работ В.А. Котельникова развивалось другое научное направление - теория помехоустойчивости.

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

В 1946 и 1956 гг. В.А. Котельниковом были опубликованы работы по оптимальным методам приема и потенциальной помехоустойчивости. Использование результатов этих работ дало возможность судить о том, насколько данная конкретная аппаратура близка к идеальной по своей способности выделять сигнал из смеси его с помехами.

Первой серьезной работой по теории передачи информации следует считать труд Р.Хартли “Передача информации”, изданный в 1928г. Немало важное значение для теории передачи дискретных сигналов имела работа Найквиста “Некоторые факторы, воздействующие на скорость телеграфирования” (1924г.).

Существенным шагом в становлении новой теории передачи информации явилась “Математическая теория связи” К.Шеннона. В этой работе доказана теорема о пропускной способности канала связи. Оказалось, что при скоростях передачи, меньших пропускной способности канала, существуют методы передачи (кодирования) и приема (декодирования), позволяющие восстановить передаваемый сигнал со сколь угодно малой вероятностью ошибки, несмотря на наличие помех.

Работы В.А. Котельникова и К. Шеннона создали фундамент теории передачи сигналов, которая получила дальнейшее развитие благодаря работам многих ученых по отдельным ее разделам.

Данные о дисциплине: Название «Теория информации».

По данной дисциплине проводятся лекционные занятия, лабораторные работы, кроме того, предполагается выполнение курсовой работы, где собирается схема с применением пакета «System View» для моделирования телекоммуникационных систем, кодирующего и декодирующего устройства циклического кода, проведение самостоятельных работ с целью углубления общих знаний теории.

Кредиты	Курс	Семестр	Лекции	Лаборат. работы	РГР	Экзамен
2	2	4	1.5 (43 час.)	0.5 (17 час.)	4	4

Временная форма

В зависимости от структуры информационных параметров, сигналы могут быть:

- непрерывные (аналоговые)

- дискретные

- дискретные-непрерывные

.

Понятие информации

Термином “информация” с древнейших времен обозначали процесс разъяснения, изложения, истолкования. Позднее так называли и сами сведения и их передачу в любом виде.

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

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

Можно выделить 3 основных вида информации в обществе: личную, специальную и массовую. Личная информация касается тех или иных событий в личной жизни человека. К специальной информации относятся научно-техническая, деловая, производственная, экономическая и др. Массовая информация предназначена для большой группы людей и распространяется через средства массовой информации: газеты, журналы, радио, телевидение.

Информация в любой форме является объектом хранения, передачи и преобразования. В теории и технике связи в первую очередь интересуются свойствами информации при её передачи и под информацией понимают совокупность сведений о явлениях, событиях, фактах, заранее не известных получателю.

Понятие помехи

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

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

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

Классификацию помех можно провести по следующим признакам:

- по происхождению (месту возникновения);

- по физическим свойствам;

- по характеру воздействия на сигнал.

Виды помех

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

(3.1)

где Т- абсолютная температура, которую имеет сопротивление R;

F - полоса частот; k =1,37*10 (-23) Вт.сек/град- постоянная Больцмана.

К помехам по происхождению, во вторую очередь, относятся помехи от посторонних источников, находящихся вне каналов связи:

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

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

- помехи от посторонних станций и каналов, возникающих от различных нарушений режима их работы и свойств каналов;

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

По физическим свойствам помех различают:

- Флуктуационные помехи;

- Сосредоточеные помехи.

Флуктуационные помехи. Среди аддитивных помех особое место занимает флуктационная помеха, которая является случайным процессом с нормальным распределением (гауссов процесс). Этот вид помех практически имеет место во всех реальных каналах.

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

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

Наиболее распространенной причиной шума являются флуктуации, обусловленные тепловым движением.

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

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

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

По характеру воздействия на сигнал различают:

- аддитивные помехи;

- мультипликативные помехи.

Аддитивной называется помеха, мгновенные значения которой складываются с мгновенными значениями сигнала. Мешающее воздействие аддитивной помехи определяется суммированием с полезным сигналом. Аддитивные помехи воздействует на приемное устройство независимо от сигнала и имеют место даже тогда, когда на входе приемника отсутствует сигнал.

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

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

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

ДРУГОЕ ДЕЛО ПОМЕХИ - ОНИ заранее не известны и поэтому не могут быть устранены полностью.

Борьба с помехами - основная задача теории и техники связи. Любые теоретические и технические решения, о выполнении кодера или декодера, передатчика и приемника системы связи должны приниматься с учетом того, что в линии связи имеются помехи. При всем многообразии методов борьбы с помехами их можно свести к трем направлениям:

- подавление помех в месте их возникновения. Это достаточно эффективное и широко применяемое мероприятие, но не всегда приемлемо. Ведь существуют источники помех, на которые воздействовать нельзя (грозовые разряды, шумы Солнца и др.);

- уменьшение помех на путях проникновения в приемник;

- ослабление влияния помех на принимаемое сообщение в приемнике, демодуляторе, декодере. Именно это направление для нас является предметом изучения.

Лекция 6. Непрерывный канал

Цель лекции: ознакомление c непрерывным каналом

Содержание:

а) разложение непрерывного сигнала в ортогональные ряды;

б) Ряды Фурье и их применение в технике связи;

в) теорема Котельникова (Основная теорема Шеннона);

г) пропускная способность непрерывного канала;

д) модель НКС.

Модель НКС

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

В канале всегда присутствуют аддитивные гауссовские помехи. Кроме гаусcовских в канале действуют помехи:

- гармонические (сосредоточенные по частоте);

- импульсные (сосредоточенные по времени);

- мультипликативные;

- перерывы связи (17,4 дБ).

К искажениям формы сигнала, также приводят:

- сдвиг частотных составляющих по частоте;

- фазовые скачки;

- фазовое дрожание.

Упрощенная модель канала представлена на следующем рисунке

Рисунок 6.2

На входе и выходе непрерывный канал связи– непрерывный сигнал, непрерывного времени.

7 Лекция 7. Методы формирования и преобразования сигналов в системах связи

Цель лекции: ознакомление с методами модуляции информации.

Содержание:

а) методы модуляции носителей информации;

б) модуляция гармонического сигнала (несущей частоты);

в) амплитудная (АМ), частотная(ЧМ), фазовая(ФМ) модуляции.

Частотная модуляция

При частотной модуляции отклонение частоты модулированного сигнала от ω_о изменяется пропорционально мгновенным значениям модулирующего сигнала u_m (t):

. (7.7)

где ∆ω_Д –коэффициент пропорциональности

∆ω_Д называют девиацией частоты и она равна наибольшему отклонению частоты несущей ω₀. Изменение частоты ЧМ сигнала графически показано на рис. 7.3, где отмечена девиация частоты ∆ω_Д, соответствующая наибольшему отклонению частоты вниз ∆ω_Д=∆ω_-, поскольку ∆ω₊ <∆ω _. Величина u_m (t) нормирована, то есть | u_m (t)|≤1.

Рисунок 7.3 - Мгновенная частота ЧМ сигнала:

а) модулирующий сигнал;

б) изменение мгновенной частоты

Девиация частоты является одним из важных параметров частотных модуляторов и может принимать значения от единиц герц до сотен мегагерц в модуляторах различного назначения. Однако, всегда необходимо чтобы выполнялось условие << .

Полную фазу ЧМ сигнала с частотой (8.7) находим путем интегрирования, т.е.

где ψ_о можно рассматривать как постоянную интегрирования.

Тогда аналитическое выражение (математическая модель) ЧМ сигнала запишется в виде

. (7.8)

Поскольку u_m (t) входит в это выражение под знаком интеграла, ЧМ часто называют интегральным видом модуляции.

Фазовая модуляция

При фазовой модуляции, отклонение (сдвиг) фазы модулированного сигнала от линейной ω₀ t +ψ₀ изменяется пропорционально мгновенным значениям модулирующего сигнала u_m (t)

. (8.9)

Где - коэффициент пропорциональности, называемый девиацией фазы. Физический смысл этого коэффициента поясняется рис.8.1, где изображены модулирующий сигнал и полная фаза ФМ сигнала. С увеличением сигнала u_m (t) полная фаза растет во времени быстрее, чем по линейному закону. При значениях сигнала u_m (t)<0 происходит спад скорости роста . Абсолютная величина отклонения (сдвига) фазы от линейной наибольшая, когда u_m (t) достигает экстремальных значений. На рис 8.1,б отмечено максимальное отклонение фазы вверх и вниз . Наибольшее отклонение фазы от линейной и является девиацией фазы . Измеряется в радианах и может принимать значение от единиц до десятков тысяч радиан.

б)

Рисунок 8.1 - Полная фаза ФМ сигнала:

а) модулирующий сигнал;

б) изменение полной фазы

Математическая модель:

(8.2)

АМ и ЧМ

Временная диаграмма АМ сигнала показана на рисунке 7.2.

Спектральная диаграмма однотонального АМ сигнала, построенная по

(8.3)

симметричной относительно несущей частоты (рисунок 8.2). Амплитуды боковых колебаний одинаковы и даже при М=1 не превышают половины амплитуды несущего колебания А₀.

Рисунок 8.2 - Спектральная диаграмма АМ сигнала при

однотональной модуляции

При гармоническом несущем сигнале временная диаграмма ЧМ:

Рисунок 8.3

Спектральная диаграмма ЧМ сигнала:

Рисунок 8.4

Векторные диаграммы АМ и ЧМ представлены на рисунке 8.5.

Рисунок 8.5 - АМ сигнал (а), ЧМ сигнал (б)

Избыточность сообщений

В качестве источника сообщений рассмотрим оператора, который вводит в компьютер текста на русском языке. Очевидно, что буквы в тексте появляются с разными вероятностями. Так, буква А передается значительно чаще чем Ц или Ю. Кроме того, появление очередной буквы зависит от предыдущей. Ясно, что после гласных не появится Ь, Ъ или Ы. Весьма редким будет появление подряд трех букв Е (в слове «змееед»). Таким образом, на выходе источника «с памятью» (зависимыми сообщениями) неопределенность оказывается меньше, чем при отсутствии памяти, когда сообщения появляются хаотично. Таким образом, мы подошли к понятию избыточности источника, которую формально можно определить соотношением:

. (10.3)

Отсюда видно, чем больше энтропия, тем меньше избыточность источника и наоборот. Ясно также, что величина избыточности принимает значения в пределах 0≤ρ≤1.

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

Избыточность можно определить так:

ρ=(n-n_min)/n=1-n_min/n. (10.4)

Величину μ=H(A)/logN=n_min/n называют коэффициентом сжатия. Он показывает, до какого значения без потери информации можно сжимать передаваемые сообщения, если устранить содержащуюся в них избыточность. Например, при передаче телеграмм из текста исключают союзы, знаки препинания которые легко восстанавливаются при чтении на основании известных правил.

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

Помимо избыточности важным параметром, характеризующим любой источник с фиксированной скоростью V_и=1/Т_и симв/с выдачи сообщений, является его производительность, которую определяют как энтропию в единицу времени (секунду):

H’(A)=V_иH(A). (10.5)

Если энтропия максимальна и равна log N, то величина R_и=logN/T_и, бит/с, называется информационной скоростью источника.

Смысл производительности – среднее количество информации, которое выдается источником в течение одной секунды непрерывной работы.

Общие сведения.

Блоковые коды

Коды обнаруживающие ошибки.

Как указывалось выше для обнаружения ошибки кодовое расстояние по Хэммингу должно быть равно: , где r – число обнаруженных ошибок.

1) Примером кода с обнаружением ошибки является код с проверкой на четность

Исходная КК	Контрольные символы	Выходная КК
00001	1	000011
00010	1	000101
00011	0	000110
00100	1	001001
00101	0	001010

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

1 -> 10 1010011 ->

0 -> 01 -> 10011001011010.

Корреляционный код содержит в два раза больше символов чем исходный, обнаружение ошибки осуществляется таким соображениями в парных элементах должны быть разные символы, т.е. элементы 00 или 11 – бракуются. Не обнаруживаются ошибки типа:

10 –> 01

01 -> 10.

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

Достоинства: нет постоянной составляющей т.к. число 1 = 0

3) Инверсный код

Информационные символы	Контрольные символы	Инверсный код
111001	111001	111001111001
101111	010000	101111010000

(Тутевич стр.65-69.)

Линейные коды.

Линейные коды - значения проверочных символов которые определяются с использованием линейных операций над определенными информационными символами.

Обычно проверочный символ m =1, если , число проверочных равенств, номера конкретных входящих в каждое проверочное равенство определяется видом и характеристиками кода.

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

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

Коды Хэмминга.

Эти коды являются примером линейных кодов, исправляющих одну единственную ошибку. Длина блока кодов удовлетворяет соотношению n=2^(n-k)-1, где n-k количество проверочных символов. Например, при n-k=3 получаем код (7,4).

Коды Рида-Соломона.

Коды РС относятся к классу недвоичных кодов БЧХ. В кодере сообщение, состоящее из k q-ичных символов, выбираемых из алфавита, содержащего q=2^m символов, преобразуется в кодовое слово РС- кода, содержащее n двоичных символов. Поскольку обычно входные и выходные алфавиты равны степени 2, то входные и выходные символы могут быть представлены m- разрядными двоичными словами. Таким образом, входное сообщение можно рассматривать как km- разрядное слово, а выходное кодовое слово – как nm- разрядное двоичное слово. Длина кода РС равна n=q-1. Если исправляющая способность кода равна t ошибочным символам, то имеет место соотношение n-k=2t. Коды РС существуют при , а их расширение имеют длины блока: n= q и n= q+1.

Код Голея.

Этот код относится к числу наиболее интересных. Он позволяет исправить ошибки высокой кратности (t>1) и является также совершенным кодом. Код Голея (23,12) является циклическим и исправляет все конфигурации ошибок, кратность которых не превышает трех. С кодом Голея (23,12) связан код (24,12), который образуется добавлением к кодовым словам кода дополнительного проверочного символа. Коды (23,12) и (24,12) имеют минимальное кодовое расстояние, равное соответственно 7 и 8. Поэтому код (24,12), кроме исправления ошибок кратности 4 при незначительном изменении кода обнаруживает ошибки выше кратности 4. Код (24,12) относится к числу наиболее распространенных.

Непрерывные коды.

Из непрерывных кодов, исправляющих ошибки, наиболее известны коды Финка-Хагельбаргера, в которых контрольные символы образуются путем линейной операции над двумя или более информационными символами. Принцип построения этих кодов рассмотрим на примере простейшего цепного кода. Контрольные символы в цепном коде формируются путем суммирования символов, расположенных один относительно другого на определенном расстоянии:

e_ik=c_i+c_k; e_i+1, _k+1=c_i+1+c_{k+1; …}

Расстояние между информационными символами l=k-i определяет основные свойства кодов и называется шагом сложения. Число контрольных символов при таком способе кодирования равно числу информационных символов, поэтому избыточность кода æ=0,5. Важное преимущество непрерывных кодов состоит в их способности исправлять не только одиночные ошибки, но и группы ошибок. Если задержка контрольных символов выбрана равной 2l, то можно показать, что максимальная длина исправляемого пакета ошибок также равна 2l при интервале между пакетами 6l+1. Таким образом, возможность исправления длинных пакетов связана с увеличением шага сложения l, а следовательно, и с усложнением кодирующих и декодирующих устройств.

Циклические коды

Любой групповой код вида (n,k) может быть записан в виде матрицы, включающий k линейно независимых строк по n символов и наоборот.

Среди различных кодов можно выделить также коды, у которых все КК могут быть получены циклическим сдвигом 1-й КК которая называется образующей. Такие коды получили название циклических.

Сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец КК.

Исх. КК 001011

Матрица КК

При построении т.о. ЦК оказывается количества КК значение меньше чем количество КК в групповом коде. Как найти общее свойство и обеспечить необходимое количество КК?

При описании ЦК КК можно представить в виде многочленов некоторой переменной х. Показатели степени у переменной х соответствуют NN разрядам (начиная с нулевого), а коэффициентами при х, в общем случае, являются элементы поля GF(q). Поэтому для двоичного ЦК коэффициентами могут быть 0 или 1.

Так, например: КК 001011 –

или .

Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью многочлена.

Циклический сдвиг многочлена без переноса “1” в конец КК можно получить простым умножением на х исходной КК:

* х

Если эти КК (001011 и 010110) сложить по m2, то результат сложения будет соответствовать умножению g(x) на (х+1):

001011

Å => х +1,

010110

011101 Å

.

Циклический сдвиг строки матрицы с “1” в старшем разряде равносилен умножению соответствующего многочлена на х c одновременным вычитанием из результата многочлена , т.е. с приведением по m2 ( ).

Т.о. любая разрешенная КК ЦК могла быть получена в результате умножения g(x) на некоторый другой многочлен с приведением результата по m( ), т.е. при соответственном выборе g(x).

1) Любой многочлен ЦК (разрешенная КК) будет делится на него без остатка.

2) Ни один многочлен, соответствующий запрещенной КК на g(x) без остатка не делится, т.е. при делении на g(x) образует остатки.

Это свойство позволяет обнаружить ошибку. По виду остатка можно определить вектор ошибки.

Свойства символического умножения.

1) Многочлен перемножается по обычным правилам, но с приведением подобных членов по m2.

2) Если старшая степень произведения не превышает n-1 то это произведение является результатом символического умножения.

3) Если старшая степень произведения n, то многочлен произведения делится на заранее определенный многочлен степени n и результатом символического умножения считается остаток от деления.

Степень остатка n-1, следовательно этот многочлен принадлежит к множеству n – разрядных КК.

Заранее выбранный элемент многочлен -> ( ),

Требования, предъявляемые к образующему многочлену.

Согласно определению ЦК все многочлены, соответственно его КК должны делится на g(x) без остатка.

Для этого достаточно, чтобы на g(x) делились без остатка многочлены составляющие образующую матрицу ЦК.

Эти многочлены получаются циклическим сдвигом, что соответствует последнему умножению g(x) на х, с приведением по модулю .

Следовательно, в общем случае многочлен g (x) является остатком от деления производной на многочлен ( ) и может быть записан так:

Т.о. образующий многочлен должен быть делением многочлена ( )

т.е входить в разложение многочлена ( ). С другой стороны при делении g (x) на образующий многочлен g(x) при ошибочном приеме должен образовываться остаток. По виду остатка происходит локализация ошибок и их исправление.

Следовательно, корректирующая способность ЦК будет тем выше, чем больше остатков образует g(x).

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

Неприводимый многочлен -> аналог простого числа (- делится только на 1 и на самого себя).

Т.о. 2 свойство образующего многочлена:

- делитель многочлена ( );

- неприводимость в поле GF(2), где определена операция суммы по m2.

Число 25 - > сложное в поле десятичных чисел.

- 1101 – неприводимый в поле GF2

1101

Å

101

111

Å

101

10 - остаток

Декодирование ЦК.

Обнаружение ошибок.

Обнаружение ошибок - достаточно просто.

Если ошибок нет =>

есть => .

При безошибочном приеме -> контрольные символы отбрасываются, информационные – используются по назначению.

Обнаружение и исправление ошибок.

Для локализации ошибок необходимо каждому вектору ошибки поставить в соответствие свой опознаватель.

Допустим:

Тогда вектор ошибки:

0000001	=>	001
0000010		010
0000100		100
0001000		011
0010000		110
0100000		111
1000000		101

Т.е. достаточно загрузить в память эту таблицу.

2-й метод.

1. Вычисление остатка:

2. Подсчет веса остатка:

-вес остатка должен быть равен или < числа исправленных ошибок

W

2a. Если условие выполняется, то

3. W > S Осуществляется циклический сдвиг КК на 1 символ влево.

Полученная КК вновь делится на g(x)

If W S. То см. пункт 2а

3а. Сдвиг вправо направленной КК на 1 символ вправо.

4. Дополнительные сдвиги влево до тех пор пока: W S

Затем п2.а

Затем повторение п.3.4 столько раз, сколько было сдвигов слева.

Пример. Принята КК: 1101110

S=1

1. Делим КК на g(x):

1101110 |1011

1011

1101

1011

1101

1011

1100

1011

111

2. Проверим вес: W=3

3. Сдвиг влево на 1 разряд:

1011101

4. Делим

1011101| 1011

1011

|101|

5. Проверим вес W=2

6. Новый сдвиг и деление:

0111011 |1011

1011

1011

1011

|001|

7. Складываем

0111011

Å

011

01110 10