Энтропия, кодирование, декодирование, линейно-групповые коды, БЧХ, коды Хаффмена, Шеннона-Фано, Хэмминга

1. ПОНЯТИЕ ИНФОРМАЦИИ . СВОЙСТВА ИНФОРМАЦИИ.

Первые попытки определить что такое информация были сделаны Хартли 1928г. – первое определение понятия “информация”. Рассмотрим определение информации данное Брилли Уэном: Допустим, что имеется задача с некоторым числом возможных ответов. Если после получения некоторого сообщения количество возможных ответов уменьшилось, то мы получили некоторую информацию о задачи. Если после получения информации ответ стал единственным, то мы получили полную информацию о задачи. Т.о. количество информации связано с числом возможных ответов до и после ее получения. Информация наряду с материей и энергией является первичным понятием нашего мира и поэтому строго не может быть определена, но можно указать ее основные свойства: 1) информация приносит знания об окружающем мире, которых в данной точке не было до ее получения, 2) информация не материальна, но проявляется в виде материальных носителей – знаков, сигналов, в форме функции времени. 3) информация заключается не только в самих знаках и символах, но и в их взаимном расположении. 4) знаки и сигналы несут информацию только для того получателя, который в состоянии их распознать. Распонать – это значит отождествить знаки и сигналы с объектами реального мира. Информация – это характеристика случайных событий и процессов.

2. ЗНАКИ И СИГНАЛЫ. СИГНАЛ, ЕГО ХАРАКТЕРИСТИКИ. КВАНТОВАНИЕ СИГНАЛОВ.

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

и по уровню. Т.к. в цифровых системах используются

только квантованные сигналы рассмотрим его

характеристику: ( Т – период квантования).

На нижнем рисунке – сигнал подвергнутый квантованию

по времени.

ТЕОРЕМА КОТЕЛЬНИКОВА: если величина T

удовлетворяет условию T≤ 1/2f0, где f0 – граничная величина спеутра сигнала, то квантуемый сигнал может быть восстановлен идеально. Все реально существующие сигналы имеют бесконечный по частоте спеутр. Поэтому f0=0, а если так, то сигнал станет непрерывным и ошибок нет. Для восстановления непрерывного сигнала по его дискретным отсчетам необходимо каждый отсчет умножить на так называемый – по функ. отсчетов и все получ. произведения сложить. М можем умножать только на положительные части – возникает погрешность. Чтобы

уменьшить ее необхоимо захватить наибоьшую

отрицательную часть , задержим на время τ. Вывод:

квантование непрерывного сигнала по времени

принципиально необходимо для работы цифровых

устройств и систем.

Квантование ведет к возникновению ошибки, которая

тем меньше, чем меньше Т. Уменьшение интервала Т

ограничивается скоростью работы машины.

КВАНТОВАНИЕ ПО УРОВНЮ:

q – шаг квантования по уровню, Х0 ≤Х≤Хмах,

n – двоичных разрядов для представленного диапозона

х, 2ⁿ представл. q = (Xmax – X0)/(2ⁿ-1), Пример:

0≤Х≤5Х, n=10, q=(5-0)/2¹⁰-1)=5mV/1дв.ед., выходной

сигнал мен., если изм. = 5 mV. Это чувствительность или разрешающая способность преобразования. ε – ошибка квантования по уровню – является случайной величиной. M[ε]=0 – мат. ожидание, D[ε] = q²/12, средне-квадратическая ошибка =√D` = q/2√3`. Вывод: квантование по уровню принципиально необходимо для работы цифровых устройств. Оно вносит ошибку, которая является случайной величиной. Ошибка тем меньше, тем больше q, т.е. чем больше уровней квантования используется. Есть также КВАНТОВАНИЕ ПО ВРЕМЕНИ И ПО УРОВНЮ.

3. СИНТАКТИЧЕСКАЯ И СЕМАНТИЧЕСКАЯ ИНФОРМАЦИЯ.

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

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

4. ЭНТРОПИЯ И ЕЕ СВОЙСВА. КОЛИЧЕСТВО ИНФОРМАЦИИ.

Главным свойством случайных событий является отсутсвие полной уверенности в той или иной их реализации, т.е. мы не можем точно предсказать исход опыта. Для разн. опытов степень неопределенности исхода опыта различна. Как зависит степень неопределнности опыта от количества возможных исходов. Очевидно, что если исход единственный, то неопределенность = 0. Если количество исходов величивается, то и неопределенность растет. Сконструируем функцию, которая позволяла бы оценивать степень неопределнности f(k), где k – количества исходов , 1) f(k=1)=0, 2) расмотрим 2 независимых опыта α, β, α – подбрасывание монеты (k=2), β – подбрасывание игральной кости (L=6). Оценить неопределнность сложного опыта, состоящего в том, что одновремено выпадает герб и 3. Очевидно, что к неопределнности 1-го опыта добавится неопределенность 2-го. Количество исходов = 12. f(kL)=f(k)+f(L), в соответствии с последней формулой в качетсве функции f можно выбрать логарифм от числа возможных исходов f=log k, чаще всего используется двоичный логарифм f=log₂ k, рассмотрим единицу 1=log₂ k, значит k=2. За единицу измерени степени неопределенности принимается неопределнность, содержащаяся в опыте с 2 разновероятными исходами (1 бит). Существуют и другие единицы 1 дит (если lg, то он 3,3333 дита).

Вероятонсть: герб – ½, цифра – 1/6, 1=log₂ 2 – общая неопределенность. Сколько неопределенности вносит каждый отдельный исход.

(1/к)log₂ k = (-1/k) log₂(1/k)= -plog₂P, вся неопределенность: H(x)=-∑[k,k=1]

Pi log₂Pi – энтропия, формула Шеннона. Пример: вероятности (1/2, 1/3, 1/6). H(x)= (-1/2)log₂ (1/2) – (1/3)… - (1/6)…

Свойства энтропии: 1) энтропия всегда положительна, 2) при Pi  0 или к 1энтропия стремится к 0. 3) найдем условие, при котором энтропия достигает максимума. {H(x)=∑[i=1, k]P1log₂P1; ∑[i=1,k]P1=1. Искать экстремум будет методом неопределенных множителей лагранжа. F=∑[i=1,k]P1 log₂ P1 + λ(∑[i=1,k]Pi -1), λ – неопределнный множитель лагранжа. Найти условие, при котором ∂F/∂P[i=1,k]=0, logPi + Pi(1/Pi)log₂e+

+λ=0, logPi= -(λ+log₂e). Поскольку справа стоит конст, то получим, что выполняется независимо от индекса i, а это возможно только если выполняется условие p1=p2..=pk.

До получения сведений энтропия системы = H(x). Предположим, что после получения сведений или сообщений неопределнность исчезла полностью. Количество информации, полученной в сообщении J(x)=Hнач(х)-Hкон(х). Если H(x) конечное =0, то количество информации, содержащееся в сообщении можно определить по той же самой формуле J(x)= - ∑[i=1,k]Pi logPi. Рассмотрим частный случай, когда все исходы равновероятны, то H(x)= -∑[i=1,k]Pi logPi = log k – формула Хартли. Пример 1: на шахматной доске находится 1 фигура. Все ее положения равновероятны. Какое количество информации содержится в сообщении о том, что фигура находится в клетке А3 (6 бит = 2⁶=64). В условии примера 1 сообщ. – фигура находится в одной из угловых клеток доски (6-2=4 вида информации). Сообщили, что фигура находится в верхней половине доски (1 бит сообщили).

8. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ДИСКРЕТНОГО СИГНАЛА.

Рассмотрим случайный сигнал, квантованный по

времени и уровню. Сигнал x(t)≤Xmax,

9=3², N=mⁿ.

0≤t≤Tсек. Если считать, что появляется переход

равер., то количество информации J=log₂N=nlog₂m,

В случае равномерного распределения сигналов

количесво информации , содержащееся в нем, прямо ~ количеству отсчетов

© http://karatel.nm.ru

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

5. ЭНТРОПИЯ НЕПРЕРЫВНЫХ СООБЩЕНИЙ (приближенная формула для энтропии свободных сигналов).

Энтропия источников сообщений описывается формулой Шеннона. H(x)=

= - ∑[i=1, n]Pi logPi, Pi – вероятность появления некоторого уровня ni сигнала. 1) если величина велика, то вычисление H(x) становится неудобным. 2) часто квантованный сигнал задается от исходного непрерывного сигнала для которого известна плотность

вероятности P(x). δi – шаг квантования. Вероятность появления

сивола Hi – вероятность того, что x(t) находится внутри δi шага

квантования, Pi – вероятность того, что Pi=p[hi – (δi/2) < x < hi +(δi/2)]=

=∫[hi +δi/2; hi – δi/2] P(x)dx. Если шаг δi мал, то можно принять, что внутри шага квантования P(x)=Pi=const => Pi=P(Hi)δi. Предположим, что δi=const, то Pi=P(hi)*δ. Подставим в исходную формулу Шеннона: H(x)=

= - ∑[i=1, n] P(hi)δ log₂(P(hi)δ). Если δ0 и n∞, то H(x)=

= - ∫[xmax, xmin]P(x) log₂(P(x)δ)dx. Учитывая вероятность появления сигнала х за пределами хмах и хмин 0, то H(x)=∫[+∞,-∞]P(x)log₂(P(x)δ)dx

9. ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА ПРИ ОТСУТСТВИИ ПОМЕХ.

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

13. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ. ФОРМУЛА ДЛЯ ПОСТРОЕНИЯ КОДА, БЛИЗКОГО К ЭФФЕКТИВНОМУ.

Кодирующее отображение X={x1,x2,…,Xr}, это B, а |m| мощность.

Кодирующее отображение В каждому Хi ставит в соответствие некоторую кодовую комбинацию длительнотсью ni из алфавита В. Оценить минимальную среднюю длину кодовой комбинации. Зная эту величину и сравнивая ее со средней длиной кодового слова реального кода, можно определить, насколько реально код близок к оптимальному. Известна вероятность P(xi), H(x)= - ∑[i=1, k] P(xi) log2 P(xi), Средняя длина n ср =

=∑[i=1,r] ni P(xi), максимальная энтропия, которую может иметь сообщение из символов алфавита В, Hmax = n ср * log2 m, т.к. Hmax≥H(x), то

n_ср *log₂ m ≥ - ∑[i=1, r] P(xi) log2 P(xi). Рассмотрим частный случай, при котором избыточность = 0. (H(x)=Hmax), ki – коэффициент избыточности.

ki=(Hmax – H(x))/Hmax), ki=(n_ср - n_min). ∑[i=1,r]ni P(xi) * log2 m =

= - ∑[i=1, r] P(xi) log2 P(xi), ∑[i=1,r](P(xi)*(ni log2 m + log2 P(xi))=0,

ni log2 m + log2 P(xi)=0, ni= - log2 (P(xi))/log2 m (**). Из (**) следует, что длина i-ой кодовой комбинации ~ (-log) вероятности появления i-го сообщения. Левая часть – целое число, правая часть – чаще всего нецелое. Полученное условие для реал. постр. эфф. кода не может быть использовано, т.к. все равенство не выполняется. Но можно потребовать, чтобы ni лежало в некотром диапозоне полученного значения, в котором обязательно найдется одно целое.

- log2 P(xi) / log2 m ≤ ni ≤ (- log2 P(xi) / log2 (m)) +1, умножим обе части на P(xi) …. - ∑[i=1, r]P(xi) log2 P(xi)/log2 m ≤ ∑[i=1,r]P(xi)ni ≤ (-∑[i=1,r]P(xi)*

*log2 P(xi)/log2 m) + ∑[i=1, r]P(xi), H(x)/log2 m ≤ n_ср ≤ (H(x)/log2 m) + 1.

Используя это неравенство можно численно оценить структурность построенного кода. Для получения эффективных кодов близких к нулю существует несколько методов (код Хаффмана, код Шеннона-Фано).

14. КОД ХАФФМЕНА. КОД ШЕННОНА-ФАНО.

Рассмотрим код Хаффмана: строится по алгоритму кодового дерева, построение графа начинается с висячих вершин. Их число соответствует количеству сообщений. Вес каждой вершины – это есть вероятность появления соответствующего сообщения. И перед началом работы висячие вершины упорядочиваются по мере увеличения высот. Шаг 1: определеяется число поддеревьев графа. Если оно меньше 2, то дерево построено, если нет – шаг 2. Шаг 2: выбирается 2 вершины с минимальными весами и сравниваются. Получаается новая вершина и 2 ребра. Новая вершина имеет вес = сумме исходных вершин. Левое ребро получается 1, правое – 0. Возврат к шагу 1. В результате построения дерева получается корень всегда = 1. Чтобы получить кодовую комбинацию i-го сообщения необходимо от корня дерева спустится по ребрам к i-ой висячей вершине, выписав при этом метки ребер этого пути. ПРИМЕР: 8 сообщений, X={x1,…x8}, B={0,1}, P(x1)=…, P(x8)=….

Пусть обратно (чем чаще сообщение, тем короче код), x1:01, x2:111, x3:110, x4:101, x5:100, x6:001, x7:0001, x8:0000. Самые мелкие вершины сращиваем

Оценим степень эффективности полученного кода. Для этого составим таблицу – (xi), (кодовая комбинация (01, 111, 110….,….)), (ni – количество символов в записи кодовой комбинации – 2, 3, 3…), (ni*P(xi)), (-P(xi)*

*log2 P(xi) *10^{- 1}). Посчитаем после n_ср = 2,92 бит, H(x)=2,85 бит.

H(x)/log2 m = n_min = 2,85 бит, Kи=(n_ср – n_min)/n_ср = 0,024, 2,4% - избыточность кода Хафмена для этого примера.

КОД ШЕННОНА-ФАНО

1) вся последовательность символов упорядочивается по убыванию значения их вероятности. 2) последовательность резбивается на 2 по возможности равновроятных группы, 3) первой группе присваивается символ “0”, второй – “1”. 4) каждая получившаяся группа развивается по возможности равновероятные и т.д. пока деление на группы возможно. Пример: 5 событий и p1=0,4, p2=0,3, p3=0,15, p4=0,1, p5=0,05.

n_ср = ∑[i=1, 5] Pi * ni = 2,05 бит,

H(x)= - ∑[i=1, 5] Pi * log2 Pi=2,01 бит,

Ки = (2,85 – 2,01)/2,05 = 0,02, 2%.

Знание эффективных кодов позволяет

ответить на впорос – какова должена

быть минимальная длина кодовых

комбинаций, чтобы передать

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

15. ГРУППЫ. ПРИМЕРЫ ГРУПП.

Группой G называется совокупность элементов, для которых определена некоторая бинарная операция и выполняются следующие аксиомы: 1) замкнутость - выбранная бинарная операция может быть применена к любым 2 элементам группы. Результат операции должен принадлежать группе. 2) ассоциативность, 3) наличие единичного элемента. В группе обязательно существует единичный элемент, причем единственный. Если выбранная операция – сложение, то единичный элемент обозначается нулем. a+0=a, 0+a=a, где a – любой элемент группы. Если умножение, то – “1”. a*1=a, 1*a=a, 4) наличие обратного элемента. Каждый элемент группы кроме единичного обладает обратным элементом. Для сложения “- a”.

Определение: группа называется аддитивной, если в качестве операции над ней используется сложение. Дальше (+) сложение по модулю 2. Группа называется абелевой, если она коммутативна: a+b=b+a, ab=ba.

16. КОЛЬЦА. ПОЛЯ.

Кольцо – абстрактное множество, которое является абелевой группой и наделенно дополнительной структурой. Кольцо L – множество с 2 опред. на нем операциями +, *. При этом справедливы аксиомы: 1) отношение “+” R является абелевой группой. 2) замкнутость a*bЄR для любых a,b из R. 3) закон ассоциативности, 4) закон дистребутивности a(b+c)=ab+ac.

Сложение в кольце всегда коммутативно, а умножение не всегда. Для произ. a и b справедливо a(-b)=(-a)b= -ab. Операция сложения в кольце имеет ед. элемент, называемый “0”. Операция * не обязательно имеет ед. элемент, если есть, то единственный. Отношение “+ “ каждый элемент из R имеет обратный. Отношение “*” обратные элементы могут существовать. Это справедливо для колец, им. ед. элемент.

b является обратным к a слева, если ba=1, c явл. обратным к а справа, если ac=1. Если одновременно существуют b и c, то а им. обратный элемент a^-1. ПРИМЕР: 1) множ. всех вещ. чисел образуют коммутативное кольцо с ед. элементом. Отн. обычных операций + и *. 2) Множ. всех целых чисел и 0 образуют коммутат. кольцо с ед. элементом. Отн. + и *.

3) Множ. всех квадр. матриц, элементами которых явл. вещ. числа, образуют некоммут. кольцо с ед. элем. отн. матр. + и *. Ед. элем. явл. ед. матрица. 4) множ. всех многочленов от некоторого элемента х с вещ. коэфф. образуют коммут. кольцо с ед. элем. отн. + и * многочленов. Ед. такого кольца является P(x)=1.

ПОЛЕ – множество элементов с 2 опред. на нем операциями, причем имеют место аксиомы. 1) множ. явл. абелевой группой по +. 2) поле замкнуто отн. умножения и образует абелеву группу по умножению. Справедливы: Дистребутивный закон. СВОЙСТВА: 1) ед. элемент отн. + обозначается 0. 2) аддитивный обратный элементу а, элемент (-a), 3) Ед. элемент для * обозн. 1, 4) обратный элем. обозначается a^-1, 5) вычитание: a+(-b), 6) деление: b^-1a. ПРИМЕРЫ ПОЛЕЙ: 1) множ. вещ. чисел, 2) множ. комплексных чисел, 3) множ. рациональных чисел. Эти примеры представляют бесконечные поля.

17. ТАБЛИЦЫ ДЕЙСТВИЙ В ПОЛЯХ GF(2) И GF(3).

Поле Галуа – конечное поле и обозначается GF(q).

Действия в полях, осн. которых явл. простые числа

(2,3,5…) выполняются по mod данного основания. Если

mod является составным числом, то действия опр-ся по

спец. правилам. Пусть F – некоторое поле. Подмнож.

в F называется подполем, если оно само является полем

отн. унаслед. из F операций. F’ – подполе. F – расширение

поля F’, а F’ – подполем поля F.

18. РАССТОЯНИЕ ПО ХЭММИНГУ. ВЕС СЛОВА. КОДОВОЕ РАССТОЯНИЕ. СВЯЗЬ ОБНАРУЖИВАЮЩЕЙ И КОРРЕКТИРУЮЩЕЙ СПОСОБНОСТИ КОДА С КОДОВЫМ РАССТОЯНИЕМ. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРИТАЦИЯ СВЯЗИ.

Расстояние по Хэмингу – ρ(v(вектор)_i, v(вектор)_j) количество различающихся позиций. Вес слова – количество единиц в слове, ω_г.

Пусть есть слова, принадлежащие коду: c1…c_k. Тогда d=ρ_min(c1c2, c2c3…,

c_k-1c_k), d – кодовое расстояние. Рассмотрим частный случай: один из векторов слова – нулевой . ρ(v(вектор)_i, 0)=ω. 1) обнаруживающая способность b – способность кода обнаруживать b и менее ошибок. 2) корректирующая способность кода t – способность кода исправлять t и менее ошибок. d≥b+1, d≥2t+1. Если d≥2t+1, то сферы не

соприкасаются, иначе возникает неопред. с1 и с2 – центры

сфер в n-мерном пространстве, представляющие кодовые

слова. Радиусы сфер t – корректирующая способность кода.

Если d≥2t+1, то сферы не соприкасаются и каждое

некодовое слово, имеющее не более t ошибок может быть

заменено кодовым, которое не является центром соответствующей сферы. Если d=2t, то сферы касаются. И если ошибочное слово находится в области касания, то неизвестно на что его заменить. Если d≤2t, то сферы имеют общий объем, внутри которого некодовые слова не могут быть исправлены.

Так как в качестве слова, например с1 может быть началом коорд., то расстояние d должно быть равно весу кодовго слова.

19. ЛИНЕЙНО ГРУППОВЫЕ КОДЫ . ПОРОЖДАЮЩАЯ МАТРИЦА, ТЕХНОЛОГИЯ ПОСТРОЕНИЯ.

Векторное пространство GFⁿ(q) представляет собой множество n-последовательностей из поля GF(q) с покомпонентным + и * на скаляр. Наиболее важен в частном случае GFⁿ(2) – векторное пространство двоичных кодов длины n, в котором при сложении 2 векторорв каждый компонент складывается по mod 2. Тогда линейный групповой код – подгруппа группы G, построен. в пространстве GFⁿ(q). Т.к. это группа, то 2 слова или 2 n-последовательности, принадл. этой группе, т.е. данному линейному коду при сложении образуют новую n-последовательность, которая вследствии свойства замкнутости также принадлежит этому коду. Произвдение любого кодового слова на любой элемент поля также принадлежит этом коду. Нулевой вектор (нулевая n-последовательность) всегда принадлежит любому линейному групповому коду.

Линейно-групповой код может быть построен на основе порождающей матрицы: G0=|| 1 0 0 (1); 0 1 0(2); 0 0 1(3)||. Все кодовые слова могут быть получены путем всевозможных сумм матрицы G0. Порождающая матрица содержит строки, которые представляют собой линейно-незавсимые векторы. Нулевая строка не может входить в порождающую матрицу.

1 – 1 0 0, 2 – 0 1 0, 3 – 0 0 1, 1(+)2 – 1 1 0, 1(+)3 – 1 0 1, 2(+)3 – 0 1 1, 1(+)2(+)3 – 1 1 1, нулевая строка – 0 0 0. Но по матрице G0 получается линейный натуральный двоичный код длины 3. Этот код не имеет избыточности, предназн. для обнаружения или коррекции ошибок. В общ. случае порожд. матрица G имеет структуру:

G=|| 1 0..0 P11 P12..P1n; 0 1..0 P21 P22...P2n; ….; 0 0..1 Pk1 Pk2…Pkn|| = IP, k – строк, n – столбцов. Единичн. матрица – информационная часть. Благодаря ее формир. слова, с помощью которых перед. информация. Подматрица P строится исходя из требований к характеристикам кода. Каждый столбец подматр. Р представляет собой сумму некот. количества информационных столбцов. Обязательно условие, чтобы каждый информационный столбец хотя бы раз участвовал в формировании проверочных столбцов. G=||100 110; 010 011; 001 101||.

Выпишем все векторы, порождаемые этой матрицей:

1 строка – 100 110 (вес 3), 2 строка – 010 011 (вес 3), 3 строка – 011 101 (вес 3), 1(+)2 – 110 101 (вес 4), 1(+)3 – 101 011 (вес 4), 2(+)3 – 011 110 (вес 4), 1(+)2(+)3 – 111 000 (вес 3), 000 000.

ω_min = 3 => d=3, 3≥b+1 (b=2), 3≥2t+1 (t=1). Код обнаруживает 2 ошибки, исправляет 1 ошибку. Могут исправляться 2,3,4,5,6 ошибки, но не обязательно.

20. ЗАДАЧА ПОСТРОЕНИЯ ЛИНЕЙНОГО ГРУППОВОГО КОДА С ЗАДАННЫМИ СВОЙСТВАМИ.

Смотри вопрос 19 и построй как там написано. Подсказка: допустим дано слово 1011011, здесь q={0,1}=2, n=7, значит GF⁷(2). Если дан многочлен, например 1x³+0x²+1x¹+1x⁰, это означает дано слово – 1011. Как строить бля? Короче надо матрицу брать, у которой по диагонали 1, а остальное 0 и скадывать ее строки, это будут кодовые слова. Есть еще один такой ебаный параметр “d” – это короче количество единиц в строке матрицы G, которая состоит из порождающей (1 по диагонали) и кодовых слов, где d подходящая (нужное количество единиц в строке + та что в порождающей).

Еще есть b (сколько ошибок обнаруживает) и t (сколько исправляет) и должно быть d≥b+1, d≥2t+1.

ЛЕКЦИЯ 6 (ВОПРОСЫ 21 – 24 ИСКАТЬ В НЕЙ)

СИНДРОМЫ.

Каждый столбец проверочной матрицы P представляет собой сумму некоторого количества столбцов информационной матрицы G. Рассмотрим принцип коррекции на примере следующей матрицы:

p1=a1(+)a2(+)a4, p2=a1+a3+a4, p3=a2+a3+a4,

(*) p1+a1+a2+a4=0 (S1), p2+a1+a3+a4=0 (S2),

p3+a2+a3+a4=0 (S3). Вектор S(S1,S2,S3) – вектор синдромов.

Вектор синдромов имеет все S1,S2,S3=0. Если выполняются

соотношения (*) , в слове нет ошибок. Система уравнений (*) является достаточной для определения существования b и меньше ошибок и исправления t и меньше ошибок. ПРИМЕР: d_min=3, t=1, b=2.

Таблица одиночных ошибок и их синдромов:

Как видно из таблицы при одиночной ошибки в любом из

разрядов вектор S не нулевой, ни один из векторов S не

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

в однозн. соответствие номер ошибочного разряда. Учитывая, что система счисления двоичная достаточно данный разряд проинверсировать и тем самым исправить ошибку. Рассмотрим парные ошибки:

Как следует из таблицы для любых парных ошибок вектор

синдромов не = 0. Это позволяет обнаружить любые

парные ошибки. Но видно, что встречаются повторяющиеся

синдромы, т.е. нельзя однозначно сказать какая пара ошибок имеет место, т.е. нельзя скорректировать эту пару. Чтобы узнать поведение

синдрома на 3, 4 и т.д. ошибки можно построить таблицы и

выписать синдромы. При наличии 3х произвольных ошибок

среди синдромов будут появляться нулевые, т.е. данный

код не обнаруживает все 3 ошибки, тем не менее

значительная часть 3х, 4х, 5ти, 6ти и одну 7ю ошибки обнаруживает.

Общий вывод: использование синдромов позволяет гарантировано обнаружить b и менее, исправить t и менее ошибок. Вместе с тем любой линейно групповой код обладает дополнительной обнаруживающей способностью большей кратности. Пример: 0011 100, S1=0, S2=1, S3=0, ошибка в p2.

ПОСТРОЕНИЕ КОДЕРОВ И ДЕКОДЕРОВ ЛИНЕЙНЫХ ГРУППОВЫХ КОДОВ

Информационное слово перед поступлением в канал связи преобразуется в кодовое слово в кодере, который должен автоматически приписать проверочные разряды к этому слову. Это можно сделать 2 путями:

1) по виду G определяется суммой каких строк является информационная часть будующего слова. Например I=0110, видно, что для матрицы это слово является суммой 2-ой и 3-ей строк.

Для получения кодового слова C(I) досттаточно сложить 2ю и 3ю строку матрицы G из прошлого примера. 2) В кодере может выполняться операция умножения. Любое кодовое слово C=I*G, C=||0110||*||G||=||0110110||.

При построении декодера можем воспользоваться 2м способами: 1) принятое слово подвергается анализу с помощью синдромов. Вместе с тем, если длина кода очень велика, то количество уравнений становится большим. 2) состоит в использовании так называемой проверочной матрицы. Ее обозначают H=||D_n-1,k I_n-k||, I – единичная матрица, D – это матрица, у которой каждая строка представляет собой проверочный столбец матрицы G. Пример: G=||100 110; 010 011; 001 101||, строка становится столбцом, H=||101 100; 110 010; 011 001||. Если слово является кодовым, то C*H^T=0. Исходя из того, что матрица I составлена из кодовых слов, произведение каждого из них на H^T равно 0, можно записать G*H^T=0 (**).

(**) является выражением, по которому однозначно можно по I построить H и наоборот.

КОД ХЭММИНГА

Наибольшее распространение среди линейных групповых кодов с использованием ошибки получили КОД ХЭММИНГА. Он имеет следующую структуру порождающей матрицы: (n, k). Код Хэмминга имеет структуру: (2ⁱⁿ - 1, 2^m-1-m), m=3,4… Если m=3, то (7,4). Если построить матрицу H для этого кода, то она будет иметь такой вид:

H=||1101 100; 1011 010; 0111 001||. Количество строк = m. Каждый разряд образует m-разрядное двоичное число. H=||6537421||. Код Хэмминга настолько популярен, что выпускаются стандартные микросхемы, поэтому когда организуется вычислительная сеть, то каждый компьютер снабжается кодером и декодером. Пользователь работает с информационными словами, но прежде чем уйти в канал связи сети, слово проходит через микросхему кодера и в принимаемом компьютере поступает в декодер.

СИСТЕМАЧЕСКИЕ И НЕСИСТЕМАТИЧЕСКИЕ

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

Различают систематические и несистематические линейные групповые коды, в том числе и код Хэмминга. В систематических кодах информационное слово занимает первые k разрядов, проверочное оставшиеся n-k. В несистематических кодах проверочные разряды вкраплены в определенные позиции кодового слова. В систематичеком коде Хэмминга вид синдрома с номером ошибочного разряда связаны через таблицу. В несистематическом коде Хэмминга вид синдрома представляется двоичным числом, которое представляет собой номер ошибочного разряда. Рассмотрим пример построения несистематического кода – построить код Хэмминга

для n=17. 1) Определяется количество проверочных

разрядов, в данном коде r ≥ ]log₂(n+1)[ - ближайшее целое

сверху. r = 5 для нашего случая.

Проверочные уравнения: a16+a17=0 (выписываем a, те где

в талице стоит единица), a8+…+a15=0 … и т.д. (всего 5).

Надо, чтобы каждый разряд вошел. a1,a2,a4,a8,16 – там

единица в столбцах по разу встречается.

Допустим a12 отказал! Смотрим столбец (01100). Чтобы найти ошибку, надо посмотреть на значение суммы строк.

ЛЕКЦИЯ 7

ЦИКЛИЧЕСКИЕ КОДЫ (ЦК)

ЦК – это разновидность линейно группового кода отн. к систематическому коду. Циклический вектор двоичного кода удобно задавать в виде многочлена (а не комбинации 0,1). F(x)=a_n-1x_n-1(+)a_n-2a^n-2(+)…(+)a1x(+)a0 (*)

х – основание системы счисления, в которой строится код. ai, где i=0,(n-1) – это цифры данной системы счисления. Например: x=3, ai=0,1,2. Мы рассм. Х=2, ai=0,1. ПРИМЕР: представить числовую последовательность в виде многочлена F(x)=1x³(+)0x²(+)0x(+)1, F(x)=x³(+)1. Представление двоичных векторов в виде многочлена позволяет перейти от действий над векторами к действию над многочленами. При этом сложение векторов предполагает сложение многочленов, которое осуществляется как сумма по модулю х одноименных коэффициентов. Умножение векторов соответствует умножению по правилу умножения многочленов, деление векторов – это деление многочленов, причем операция “-“ преобразуется в операцию “+” по модулю. F1(x)=x³+x²+1, F2(x)=x+1.

1) F1(x)+F2(x)=x³+x²+x (в двоичной системе 1+1=0), 2) F1(x)*F2(x)=

=(x³+x²+1)(x+1)=x³+x³+x³+x²+x+1=x⁴+x²+x+1,

3) F1(x)/F2(x)=x².

Основным свойством циклического кода

является: если некоторый вектор принадлежит

циклическому коду, то любой другой вектор,

полученный из данного путем произвольного

числа циклических сдвигов также принадлеэит

циклическому коду. Идея построения циклического кода базируется на понятии неприводимого многочлена, который делится только на самого себя и на единицу, т.е. не может быть разложен на более простые многочлены. Сам же неприводимый многочлен является делителем многочлена xⁿ(+)1 без остатка. Неприводимые многочлены в теории циклических кодов играют роль образующих многочленов или полиномов. Эти полиномы табулированы. P(x)=x+1, P(x²)=x²+x+1, P(x³)=x³+x+1, P(x⁴)=x³+x²+1. Вектор циклического кода по заданному информационному слову строится следующим образом:

Пусть задано информационное слово Q(x) и многочлен P(x^r ). Тогда, когда слово F(x)=Q(x)*x^r + Res [Q(x)x^r / P(x^r )], Q(x) – информационное слово, которое надо закодировать. P(x) – порождающий многочлен. Пример (КОДИРОВАНИЯ В ЦИКЛИЧЕСКОМ КОДЕ): число, которое подлежит кодированию – 0111. P(x³)=x³+x²+1, Q(x)=x²+x+1, r = 3, Q(x)*x^r = x⁵+x⁴+x³, P(x)=x⁵+x⁴+x³+R, столбиком делим Q(x)*x^r / P(x^r ) = x²+1, остаток R=1.

ОТВЕТ: F(x)=x⁵+x⁴+x³+1 => 0111 001.

Циклический код, как и всякий систематический код код может быть задан в виде порождающей матрицы. Структура этой матрицы:

G_{(n, k)} = ||I^T_{k x k}, P_{k x (n-k)}||, P – матрица проверочных разрядов.

ПРИМЕР: ПОСТРОИТЬ МАТРИЦУ G(7,4) ЦК

Q1(x)=1, Q2(x)=x, Q3(x)=x², Q4(x)=x³.

P(x³)=x³+x²+1, Чтобы найти значения, которые потом

вписать в правую часть матрицы, надо произвести

деления столбиком и найти остатки, которые потом в

соответствии с присутствующими степенями х преобразовать в двоичный вид и записать в правую часть. Res[Q(x)x³/P(x³)] - ? Надо 4 раза поделить.

Делим на P, соответственно x³, потом x⁴, x⁵, x⁶.

29. АЛГОРИТМ ПОСТРОЕНИЯ ЦК С ЗАДАННЫМИ СВОЙСТВАМИ

Как в любом коде, порождаемом матрицей все кодовые слова могут быть получены как все возможные линейные комбинации строк матрицы. Построение ЦК с заданными свойствами связано с выбором порождающего многочлена. В первую очередь это степени полинома n, которая равна количеству столбцов порождающей матрицы. Степень r определяется по специальным таблицам, в которых связаны следующие характеристики кодов: n – длина кода, k – количество информационных разрядов, d – кодовое расстояние => r. Рассмотрим принцип построения таблиц. Если имеется r проверенных разрядов, то это число степеней свободы. Если код должен иметь t=1, то 2^r – 1 ≥ C¹_m (количество одиночных ошибок), если t=2, то 2^r –1 ≥ C¹_m+C²_m, r ≥ ]log₂(C¹_m+…+C^t_m+1)[. После получения порождающей матрицы G по заданному неприводимому полиному и по исходным требованиям осуществляется проверка полученного решения. Проверяется вес каждой строки порождающей матрицы ωi ≥ dmin. Расстояние по Хэммингу между любой парой строк в порождающей матрице должно быть не меньше dmin. Если хоть одно условие не выполнится, то необходимо заменить неприводимый многочлен P(x^r ), либо на другой многочлен этой же степени, либо на многочлен большей степени.

31. АЛГОРИТМ КОРРЕКЦИИ ОШИБОК В ЦК.

Любое кодовое слово ЦК делится на неприводимый многочлен без остатка, поэтому признаком наличия ошибки в принятом слове является ненулевой остаток от деления принятого слова на неприводимый многочлен. Однако наличие ненулевого остатка лишь говорит о факте существования ошибки, т.е. ошибки обнаруживаются, но по виду остатка нельзя судить о месте возникновения ошибки. Для коррекции t и менее ошибок используется следующий алгоритм: 1) принятое слово делится на неприводимый полином. 2) подсчтывается вес остатка. Если он не превышает t, то остаток суммируется с делимым и полученная сумма – есть правильное слово. Если вес остатка больше t, то принятое слово циклически сдвигается влево на один разряд , делится на P(x^r ) и анализируется вес остатка. Если вес остатка не больше t, то остаток прибавляется к делимому. Полученная сумма циклически сдвигается вправо на один разряд. Результат этой операции – скорректированное слово. Если вес остатка больше t, то делимое еще раз сдвигается влево. ПРИМЕР: ЦК задан порождающей матрицей G=

P(x³)=x³+x²+1, t=1. Кодовое слово: A=0001101, слово с ошибкой

A’=0011101=x⁴+x³+x²+1, делим столбиком A’/ P =x, остаток

Res=x²+x+1, ω(Res)=3>t (исправлять не надо). Теперь сдвигаем

A’¹ (сверху стрелка ) = 0111010, и опять также делим Res=x+1 (ω=2)>t, опять значит не то – сдвигаем опять влево и так далее, пока не станет Res=1 (ω=1=t). Исправляем последний символ A’³() на обратный и двигаем  на 3. Это будет A!

ТЕХНОЛОГИЯ КОДИРОВАНИЯ.

СИСТЕМАТИЧЕСКИЙ, НЕСИСТЕМАТИЧЕСКИЙ ЦК

ЦК можно построить как систематический, так и несистематический. Систематический строится в соответствии с C(x)=Q(x)*x^r (+)Res[Q(x)x^r /

/ P(x^r )]. Чтобы построить в несистематическом: C1(x)=Q(x)*P(x). Для реализации кодирования и декодирования используются специальные регистры сдвига с обратными связями или без них, которые в зависимости от конкретной схемы реализуют либо умножение, либо деление на порождающий многочлен (декодирование).

32. СХЕМЫ АППАРАТНОЙ РЕАЛИЗАЦИИ КОДЕРОВ И ДЕКОДЕРОВ ЦК. ДЕКОДЕР МЕГГИТА.

Рассмотрим основные структуры кодеров и декодеров циклических кодов. Схемы, построенные на основе регистров сдвига называются цифровыми фильтрами. Основа – циклический сдвиг. Чаще всего это D-триггер. n-разрядный регистр сдвига исползуется для циклического сдвига многочлена xⁿ-1. Каждый раз после сдвига вычисляется x*V(x)(mod(xⁿ-1)),

V(x) – некоторый начальный вектор, который помещен в этот регистр. Структура определяет выражение по модулю xⁿ-1, где n – количество регистров. х – умножение, в логике – сдвиг. Умножение на х соответствует однократному циклическому сдвигу V(x) вправо, причем старшие разряды слова находятся справа. Регистр сдвигов с обратнми связями относится к классу рекурентных фильтров. Если фильтр построен только с прямыми связями, то он называется фильтром с конечным импульсным откликом (КИО-фильтр; нерекурсивный фильтр).

g(x) – порождающий многочлен,

g(x)=g_L * x^L + …+g2x²+g1x+g0x⁰.

Коэффициенты g_i – весовые коэф-

фициенты порождающего многочлена

g(x) и они равны весовым множителям в подводах регистра сдвига.

Для поля GF(2) эти коэффициенты равны 0 или 1, что соответствует наличие или отсутствию соответствующей связи. Пусть есть некоторая входная последовательность a(x)=a_k x^k +a_k-1 x^k-1+…+a1x+a0,

b(x)=b_k+L x^k+L + b_k+L-1 x^k+L-1+…+b1x+b0, b(x) – выходная последовательность фильтра. Процессы, описываемые в этой схеме  b(x)=g(x)a(x). При условии, что начальное состояние регистра – нуль и после ввода элемента

a0 в схему вводится еще L нулей. Данная структура представляет устройство перемножения 2х многочленов, один из которых g(x) задан жестко структурой фильтра, а 2-ой a(x) является произвольным входным многочленом. Рассуждая в терминах циклических кодов можно сказать, что данная схема является КОДЕРОМ НЕСИСТЕМАТИЧЕСКОГО КОДА с порождающим многочленом g(x), а а(х) – это есть информационное слово, подлежащее кодированию. Общая формула: b_j = ∑[i=1,n] g_i a_j-i.

ПРИМЕР: g(x)=x⁸+x⁷+x⁴+x²+x+1.

Так как процесс декодирования связан

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

Обобщенная схема делительного устройства: Данная схема делит входной полином на порождающий многочлен g(x). В начальном

состоянии все триггеры сброшены и первые

r сдвигов на выходе последнего триггера 0, т.е.

обратная связь разомкнута. Многочлен

d(x) проталкивается в схему начиная со

старших коэффициентов. После n сдвигов, где n – степень многочлена d(x) на выходе схемы будет частное, a в самом регистре будет записан остаток от деления d(x) на g(x). g(x)=g_r x^r + …+g1x+g0.

d(x)=11000001, d(x)()=10000011.

Результат – остаток 110011 (x⁵+x⁴+x+1).

Делительногое устройство, построенное для заданного

порождающего многочлена является универсальным ядром

любого кода, использующего данный попрождающий

многочлен, т.е. такие схемы универсальные. Но рассмотренная

структура фильтра имеет недостаток, что между элементами

памяти в определенных точках вставляются сумматоры по mod 2. Это нарушает регулярность структуры, поэтому используются и другие схемы, в которых существуют только непосредственные связи между элементами памяти, а сумматоры по mod 2 находятся в цепях обратной связи. Описанные цифровые фильтры используются в качестве основных элементов кодеров / декодеров ЦК. При несистематическом кодировании информационное слово, поступая на bx КИО-фильтра, кодируется и на выходе фильтра получается кодовое слово. ПРИМЕР построения кодера для кода Хэмминга 15.11: g(x)=x⁴+x+1.

Для кодирования непрерывного потока

информационных слов таким кодом

Хэмминга вся последовательность

сообщений разбивается на блоки, каждый из которых содержит по 11 информационных разрядов и между блоками включается по 4 нуля, результирующий поток пропускается через данный КИО-фильтр. На выходе фиьтра получается непрерывный поток непересек. пятнадцатиразр. кодовых слов в коде Хэмминга. Чтобы получить СИСТЕМАТЧЕСКИЙ код, необходимо воспользоваться другой схемой: C(x)=Q(x)x^r + R[Q(x)x^r /

/ g(x)]. Для реализации необходимо скомбинировать схему умножения на x^r (сдвиг на r-разядов) с вычислением остатка от деления на порождающий многочлен. Рассмотрим КОДЕР ХЭММИНГА 15.11, ВЫРАБАТЫВАЮЩИЙ СИСТЕМАТИЧЕСКИЙ КОД:

11 разрядов информационного слова

Q(x), начиная со старших разрядов,

вводится в цепь деления на

порождающий многочлен g(x).

умножение на x⁴ учит. первыми 4 вспом. тактами, в течении первых 11 тактов через нижний ключ, находящимся в нижн. положении на вых. C(x) поступает информационное слово Q(x), после чего этот ключ перебрасывается вверх на последн. 4 такта. За 15 сдвигов (11 инф + 4 вспомогат) в делит. устройстве вычисляется остаток. После 15 такта ключ обр. связи размыкается и за доп. 4 такта вычислен. значение остатка из регистра делительного устройства проталкивается на выход C(x). После 19 тактов на выходе C(x) сформир. слово систематич. кода Хэмминга 15.11.

ЛЕКЦИЯ 9.

ДЕКОДИРОВАНИЕ В ЦК осуществляется на основе остатка от деления принятого слова на порождающий многочлен. Если кодовое слово C(x), V(x)=C(x)(+)R(x), R(x) – вектор ошибки. Остаток от деления V(x)=Res_g(x)(C(x)+e(x))=Res_g(x)(C(x)) + Res_g(x)(e(x)). Вид остатка от деления, принятого многочлена на порождающий многочлен g(x) определяется только вектором ошибок e(x) и не завсисит от кодового слова. Структурная схема ДЕКОДЕРА (15.11):

Информационное слово

V(x) поступает на вход

регистра сдвига 2, где за

15 тактов полностью

его заполняет.

Одновременно верхн.

часть схемы,

представляющая собой делитель на порождающий многочлен кода 15.11, осуществляет деление, и после 15 тактов в нем остается остаток. Этот остаток в качестве адреса поступает в ПЗУ, в котором по каждому адресу записано слово ошибки e(x), соответствующее данному остатку. Это слово выбирается из ПЗУ и записывается в регистр сдвига 1. В течении следующих 15 тактов регистры 1 и 2 сдвигают содержимое. На элементе суммир. осуществляется V(x)+e(x) или С(х)+e(x)+e(x)=C(x). Одновременно C(x) поступает на 2 делительное устройство, на выходе которого получается 11 разрядное инф. слово. Основной минус данной схемы – необх. иметь ПЗУ, в котором размещается таблица соответствия вида остатка и вектора ошибок e(x). Когда коды сравнит. небольшие, то это недостаток непринцип., но при больших кодах это неудобно. Поэтому чаще используются специальные декодеры МЕГГИТА. В декодере Меггита синдромы вычисляются только для тех конфигураций ошибок, которые находятся в старших разрядах слова. Декодирование в ост. аозициях базируется на циклической структуре кода и осуществляется позже. Таблица синдромов содержит только те синдромы, которые соответствуют ошибкам старших разрядов. Если код испр. одиночн. ошибку, то требуется запомнитьь 1 синдром. Если вычисленный остаток совпадает с запомненным, это означает, что ошибка в старшем разряде. Если остаток не совпадает с запомненным, то осуществляется сдвиг остатка и выдвигается гипотеза об ошибке в (n-1) разряде. Если синдромы совпали, то этот разрядд исправл., иначе – очередной сдвиг и анализ (n-2) разряда и т.д. Эта действия базируются на т.Маггеита. R_g(x)[V(x)]=S(x)=R_g(x)[x e(x)],

R_g(x)[x V(x)](mod xⁿ-1)=R_g(x)[x S(x)]. Эта теорема говорит о том, как надо вычислять синдром произвольного циклического сдвига конфигурации ошибки по известному синдрому, который связан с известной ошибкой. В качечтве табличных выбираются синдромы, соответствующие исправляемым ошибкам старших разрядов.

Обобщенная труктурная схема декодера:

В начале работы декодера содержимое всех

регистров равно 0, после n-тактов слово V(x)

заполнило буферн. регистр сдвига, а в верхн.

регистре – остаток от деления на g(x).

Вычисленный синдром сравнивается со всеми

запомненными табл. синдромами (если t=1, то запомнен 1 синдром для n-1 разряда, если t=2, то 2 синдрома для n-1 и n-2 разряда и т.д.). В случае совпадения синдрома с одним из хранящихся в памяти символы, нахдщихся в крайнем правом разряде буфера, исправляются. Синдромный и буферный регистры 1 раз сдвигаются. Это соовтетствует выполнению условия теоремы Меггита. Если новый синдром совпадает с каким-либо из запомненных в таблице, то исправляется соотв. крайний правый разряд буфера и т.д.

25,26. БЧХ-КОДЫ

Это обширный класс кодов, способный исправить несколько ошибок. Интерес к этим кодам обусловлен : 1) среди кодов БЧХ при небольш. длинах существуют достаточно хорошие коды. 2) известны относительно простые методы кодирования и декодирования БЧХ-кодов 3) это широко известный подкласс недвоичных кодов, обладающий определенными оптимальными характеристиками. 4) полное понимание БЧХ кодов позволяет сравнительно легко и просто строить и анализировать другие виды кодов. Определим коды БЧХ, исправляющего t над полем GF(q) с длинной кодовых слов q^n-1 (примитивный код). g(x) – порождающий многочлен. Основная задача при построении БЧХ кода – построение g(x). В теории БЧХ g(x) строится: g(x)=НОК[f1(x), f2(x), …, f_r (x)]. Многочлен f1(x), f2 и т.д. – это минимальные многочлены корней g(x). Используя это представление будем строить g(x) по его корням. Пусть C(x) кодовый многочлен e(x) – многочлен ошибок, v(x) = C(x) + e(x) – принятое слово. Можно вычислить значение этого многочлена на элементах расширения поля GF(q^m), нас будет интересовать значение v(x) в точках х=γ1, γ2…, γ_r, где γ_j – корни g(x), v(γ_j)=C(γ_j)+e(γ_j). Поскольку γ_j – один из корней g(x), то C(γ_j)=0, v(γ_j)=e(γ_j). Значение принятого вектора при х=γ_j. Определяется только вектором ошибок в этой же точке и не зависит от кодового многочлена. Т.к. j изменяется от 1 до r, то мы имеем систему из r уравнений. Если эту систему можно разрешить относительно компонентов е, то полностью обнаруживается вектор ошибок. Задача – так выбрать γ_j, чтобы эта система была всегда разрешима относительно компонентов вектора е при условии, что вес вектора е не превышает t. Решением этой задачи является выбор γ_j в виде степеней примитивных элементов {α, α²,…, α^2t}, α – примитивный элемент поле GF(q^m). Примитивным элементом над GF(q^m) называется такой элемент поля α, что все остальные элементы этого поля, кроме 0 могут быть получены как степени элемента α. ПРИМЕР: GF(5). 0,1,2,3,4 (по mod 5). 2⁰=1, 2¹=2, 2²=4, 2³=3, 2⁴=1, 2⁵=2, 2⁶=4, 2⁷=3 и т.д. 2 – примитивный элемент поля GF(5). Примитивные элементы очень полезны при построении полей, так как зная его можно достроить все поле. Справедливы следующие теоремы относительно простых элекментов:

1) пусть β1, β2…β_q-1 – ненулевые элементы поля GF(q). Тогда справедливо x^q-1-1=(x-β1)(x-β2)…(x-β_q-1). ПРИМЕР: GF(5)

x⁴-1=(x-1)(x-2)(x-3)(x-4)=(x²-2x-x+2)(x²-4x-3x+12)=(x²-3x+2)(x²-2x+2)=

=x⁴-2x³-2x²-2x³+6x²-6x+2x²-4x+4=x⁴+4, x⁴-1=x⁴+4 (4+1=0), x⁴=x⁴.

2) Группа ненулевых элементов поля GF(q) является циклической. 3) в каждом поле GF имеется примитивный элемент. Рассмотрим поле GF(8), которое можем построить с помощью многочлена P(z)=z³+z+1. P(z) – это примитивный многочлен над полем GF(q), так что в расширении поля, построим по mod p(z) элемент z является примитивным. Точно также как поле целых чисел может быть построено как

степени примитивного элемента, также поле

многочленов может быть построено как степени

примитивного элемента, соответств. выбраному

примитивному многочлену 

α1=mod(z/(z³+z+1))=z, остальные α до α7

находим тоже делением, но каждый раз степень

z в числителе увеличивается на 1.

Умножение в поле выполняется просто:

α4*α6=(z²+z)(z²+1)=α10=α7*α3=α3=z+1

В этом представл. умножение выполняется легко.

GF(8)=2³, m=3. Расширение поля GF(2).

GF(16)=GF(2⁴), m=4, длина кода q^m-1=15. Для поля GF(16) выбираем примитивный многочлен z⁴+z+1 и примитивный элемент z.

Код БЧХ строится в следующей

последовательности: 1) задаем длину кода

n=2^m-1, число ошибок t для коррекции. 2)

выбираем примитивный многочлен степени m. 3)

на его основе строится расширение поля GF(q^m)

4) находим минимальные мнгочлены вида f_j(x),

jЄ[1;2t], 5) строим g(x)=НОК(f1(x)…f_2t (x)).

Построенные таким образом коды БЧХ на самом деле могут исправить больше t ошибок, поэтому d=2t+1 – конструктивное расстояние кода. Истинное кодовое расстояние может быть больше. Построим представл. поля GF(16) как расширение поля GF(2), по примитивному многочлену p(z)=z⁴+z+1.

Минимальные многочлены –

многочлены над полем

GF, для которого

f(β)=0, где β – соотв.

элемент поля (корень).

Среди многочленов f(x)

встречаются повторяющ.,

что резко облегчает постр.

g(x). Если взять некот.

элементы β и β², их простые

многочлены совпадают.

Строим

g(x)=НОК(f1(x)…f_2t(x)),

Пусть t=2, тогда

f1(x), f2(x), f3(x), f4(x),

т.к. f1=f2=f4, то

g(x)=(x⁴+x³+x²+x+1)(x⁴+x+1) = x⁸+x⁷+x⁶+x⁴+1 …………………………………

структура (15,7). Построим БЧХ-код ддлины 15 и t=3. Тогда g(x)=НОК(f1f2f3f4f5f6)=НОК(f3f4f5)=(x⁴+x³+x²+x+1)(x⁴+x+1)(x²+x+1)=

=x¹⁰+x⁸+x⁵+x⁴+x²+x+1, (15, 5) три ошибки, t=4, g(x)=(∑[i=1, 14]xⁱ ), код (15,1). t=5,6,7, g(x) = ∑[i=1, 14]xⁱ код (15,1). Это является фактич. кодовое расстояние d оказывается больше конструктивного. При t>7 код БЧХ не определен, т.к. поле GF(16) имеет всего 15 ненулевых элементов и такая задача теряет смысл.

ДЕКОДИРОВАНИЕ БЧХ-КОДОВ

Т.к. БЧХ – ЦК, то он может быть декодирован, как любой другой ЦК. Существуют специальные приемы, основанные на свойствах полей Галуа, которые позволяют декодировать БЧХ коды другими методами.

© http://karatel.nm.ru

ЗАДАЧИ © http://karatel.nm.ru

1) Оценить вероятность, что при передаче сообщения из N символов n из них будет искажено при условии, что вероятность искажения одиночного символа p (L из них искаженные), p0 – вероятность, что нет искажений.

p0=(1-p)^N. p1 – вероятность произвольной одиночной ошибки, при условии, что все остальные символы правильные.

p1=Np(1-p)^N-1, p2=C²_N p²(1-p)^N-2=(N(N-1)/2)*p²(1-p)^N-2, P_L = C^L_N p^L*

*(1-p)^N-L=(1/L(n-L))p^L(1-p)^N-L. N=16, p=10^-3, L=1, L=2, p1=…, p2=…

p1/p2=100.

2) Оценить разрешающую способность квантователя сигналов по Борну для следующих данных: x_min≤x≤x_max, Xmax=10В, Xmin=5В, n=12.

q=(Xmax – Xmin)/(2ⁿ-1)=1,2*10^-3

3) Вычислить энтропию? H(x)= - ∑ Pi log₂ Pi (без калькулятора - пиздец).

Единица измерения – бит.

4) Имеется 2 емкости с шарами одинакового объема, но разной массы. Из каждой емкости выбирают по одному шару. Выбор шара из какой емкости следуюет считать более неопределенным? Неопределенность – это энтропия (см. пункт 3). Шары с массами 1, 2, 3. В 1 банке их соответственно 10, 15, 25 штук, во 2 банке их 15, 18, 32 штуки. Вероятность, что достанут какой-нибудь шар =1. Что его масса будет 1 из 1-ой банки вероятность =0,2, потом что 2 = 0,3, что 3 =0,5 (0,2+0,3+0,5=1). И так же для 2-ой банки. Потом по формуле находим энтропию.

5) Какое количество информации содержится в сообщении о том, что школьник получил оценку 5, если все варианты равновероятны?

Количество информации I(x) = H(x)_н – H(x)_к, где н/к – начало/конец.

Если все варианты равновероятны, то по формуле Хартли H(x)=log₂K, где K – количество вариантов. log₂4=2 бита информации.

6) Реальная пропускная способность канала связи определяется по формуле: n/T=(C/H) – ε. Определить величину ε при следующих условиях: P(x1)=0,4, P(x2)=0,3, P(x3)=0,2, P(x4)=0,1, C=1000 бит/сек. H(x)=…, C/H=…=575.

Повысится ли ε, если применить код Хафмана? Ответ: Да!

7) Определить эффективность введения временной избыточности. N=(2S+1), где s=1,2… Если S=1, то N=3 и код с утроением.

Задание – оценить вероятность принятия неправильного решения для кода с утроением при вероятности одиночной ошибки p<0,5.

000, 001, 010, 011, 100, 101, 110, 111. Там где больше одной единицы – неправильные. p1=3p²(1-p), Для 111: p2=p³, p=…=p(3p-2p²)=10^{- 3}.

8) Синтезировать матрицу, удовл. этим требованиям.

Сколько проверенных разрядов?

d=2t+1, t=(d-1)/2, 2^n-k-1≥C¹_n, 2³-1=n, n=5, 2²-1≠5, n=6,

2^6-3-1≥6, 7≥7 подходит => +3 стр., чтобы 6 разрядов.

9) Декодирование: