🗊Презентация Программная реализация кода с повторением

Программная реализация кода с повторением Код с повторением без инверсии является систематическим разделимым линейным циклическим (n,k)-кодом, содержащим информационных и r = k проверочных символов (при одном повторении). Длина кода n = k + r. Особенность кода состоит в том, что в нем проверочные символы являются просто повторенными информационными символами, т.е. в рамках ТЛ3 bj=aj (j=1÷k). Код имеет и применяется для обнаружения ошибки.

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

Перенос данных с листа 1 Sheets("Лист1").Select Период = Sheets("Лист1").Cells(2, 4).Value Длит = Sheets("Лист1").Cells(3, 4).Value ДлинаКода = Sheets("Лист1").Cells(5, 3).Value Код = Sheets("Лист1").Cells(5, 4).Value ЧислоПовт = Sheets("Лист1").Cells(5, 8).Value Среднеквадратичное отклонение шумового сигнала Sr = Sheets("Лист1").Cells(5, 10).Value

Формирование кода ШагВр = Период / ЧислТочНаПериод For i = 0 To ЧислТочНаПериод - 1 t = i * ШагВр For j = 1 To ДлинаКода 'Интервал информационных символов НачИС = (j - 1) * Длит КонИС = j * Длит Символ = Mid(Код, j, 1) If t >= НачИС And t <= КонИС Then u = CInt(Символ) End If Next j Пр(i) = u 'Запись для графика процесса на одном периоде Sheets(2).Cells(i + 3, 1).Value = CSng(i) * ШагВр Sheets(2).Cells(i + 3, 2).Value = Пр(i) Next i

Построение графика периодической функции 'Число точек графика ЧислТочГраф = CInt(ЧислоПовт * ЧислТочНаПериод) ГрафШагВр = ЧислоПовт * Период / ЧислТочГраф For i = 0 To ЧислТочГраф 'Формирование временной оси на графике 'область по времени от 0 до ЧислТочГраф ' Время = (CSng(i) - ЧислТочНаПериод * (1 - Длит / (2 * Период))) * (Период / ЧислТочНаПериод) ВремяГраф = CSng(i) * ГрафШагВр Sheets(2).Cells(i + 3, 3).Value = ВремяГраф 'Сигнал - процесс на интервале графика Sheets(2).Cells(i + 3, 4).Value = Пр(CSng(i) Mod ЧислТочНаПериод) + Application.NormInv(Rnd(7), 0, Sr) Next i

Подготовка к суммированию повторных сигналов 'Сумма сигналов (повтор) ReDim Sign(16) As Single 'Очистка листа 4 Sheets(4).Select Sheets(4).Cells.Select Selection.ClearContents For i = 0 To ЧислТочНаПериод - 1 Sheets(4).Cells(i + 1, 1).Value = Sheets(2).Cells(i + 3, 3).Value Sheets(4).Cells(i + 1, 12).Value = Sheets(2).Cells(i + 3, 3).Value Sign(1) = Sheets(2).Cells(i + 3, 4).Value Sheets(4).Cells(i + 1, 2).Value = Sign(1) Next i

Подготовка к суммированию повторных сигналов 'Перенос на лист 4 For j = 1 To ЧислоПовт - 1 For i = 0 To ЧислТочНаПериод - 1 k = i + 3 + ЧислТочНаПериод * j Sign(j) = Sheets(2).Cells(k, 4).Value Sheets(4).Cells(i + 1, j + 2).Value = Sign(j) SSign = SSign + Sign(j) Next i

Вычисление среднего значения по повторам For i = 0 To ЧислТочНаПериод - 1 SSign = 0 For j = 1 To ЧислоПовт Sign(j) = Sheets(4).Cells(i + 1, j + 1).Value Sheets(4).Cells(i + 1, j + 7).Value = Sign(j) SSign = SSign + Sign(j) Next j Sheets(4).Cells(i + 1, 13).Value = SSign / ЧислоПовт Next i

Сигнал + шум после усреднения 2-х выборок

КОД С ПОВТОРЕНИЕМ И ИНВЕРСИЕЙ Код с повторением и инверсией является систематическим разделимым нециклическим нелинейным (2k,k)-кодом. Имеет k информационных и r = k проверочных символов. Отличается от кода с повторением (однократным) без инверсии тем, что значение проверочных символов в нем зависят от значения сумм по модулю два всех информационных символов. Если т.е. если число единиц в информационной части кода четно, то проверочные символы повторяют информационые:

Если, то есть, если число единиц в информационной части кода нечетно, то проверочные символы повторяют информационные в обратном (инверсном) коде с заменой 0 на 1 и 1 на 0, а именно b j= aj Å1 (j = 1÷k). Замена в i-том символе 0 на 1 или 1 на 0 равносильна его сложению по модулю 2 с единицей,

Процедура обнаружения ошибок Корректирующая способность кода: код позволяет обнаруживать ошибки любой кратности, за исключением таких, когда искажены два информационных символа и соответствующие им два проверочных символа, четыре информационных символа и соответствующие им четыре проверочных символа, то есть четное число информационных и соответствующие им проверочные символы (a1, a2 и b1, b2; a1,a3 и b1 , b3; a2 ,a3 и b2 , b3 и др.). Процедура обнаружения ошибок сводится к следующему. Одноименные информационные и проверочные символы принятой комбинации сравниваются между собой, причем, если сумма по модулю два всех информационных символов равна 0, то проверочные символы подаются в устройство сравнения в прямом коде (как были приняты), если же эта сумма равна 1, то проверочные символы подаются в указанное устройство в обратном (инверсном коде).

В результате сравнения формируется синдром ошибки S=SrSr-1…Si…S1, Si=1 (i = r÷1), если соответствующие информационные и проверочные символы в устройстве сравнения не совпадают, Si =0, если совпадают. Значение Si находится как сложение по модулю два i –ых информационных и соответствующих им проверочных символов. S1 = a1* b1* , S2 = a2* b2* , S3= a3* b3*, при четном числе единиц в информационной части кода. при нечетном числе единиц в информационной части, где черточка над символом обозначает знак инверсии, что равносильно сложению по модулю два символа с 1,

Процедура обнаружения и формирования синдрома ошибки рассмотрим на следующих примерах: передавалась комбинация Vi=110110. В процессе передачи искажен первый символ, вектор ошибки ei=100000. Принята комбинация Vi*=010111. В информационной части нечетное число единиц. Инвертируем проверочную часть и анализируем полученную комбинацию 010000. Находим синдром ошибки S Откуда S=S3S2S1 = 010 указывает на наличие ошибки.

Имеется ошибка четвертой кратности Передавалась комбинация Vi=110110. В процессе передачи искажены первые и третьи символы как в информационной так и в проверочной части. Вектор ошибки ei=101101. Полученная комбинация Vj=011011. В информационной части четное число единиц. Инверсирование не требуется. Анализируем принятую комбинацию и находим синдром S. Синдром S=S3S2S1=000 указывает, что ошибки нет. Но на самом деле имеется ошибка четвертой кратности, но она не обнаруживается и осуществляется ошибочный прием.

Вероятность появления ошибок комбинации на выходе устройства обнаружения ошибок при одноразовой передаче комбинации по двоичному симметричному каналу (ДСК) или вероятность необнаружения ошибок Рн и равна вероятности появления четного числа (2,4,6 …) ошибок в информационной части кода и соответствующих им ошибок в проверочной части кода. где р – вероятность искажения одного символа, q=1-p – вероятность правильного приема одного символа.

КОРРЕЛЯЦИОННЫЙ КОД - КОД С УДВОЕНИЕМ ЭЛЕМЕНТОВ Этот код является разделимым, не систематическим, длины n с k – информационными и r = k проверочными символами, n =k + r = 2k . Построение данного кода заключается в следующем: Проверочные символы формируются по соответствующим информационным символам и занимают позиции сразу за информационными символами. Значение проверочного символа инверсно по отношению к информационному.

Процедура построения Строится первичный (обычный двоичный) код длины k. Затем производится его перекодирование по следующему правилу: 1 заменяется двумя символами 10, первый символ – информационный, второй символ – проверочный. 0 заменяется 01. Структура комбинации выглядит следующим образом: а1b1a2b2 a3b3 и т.д. на нечетных позициях располагаются информационные символы, на четных – проверочные символы. Пример построения кодовой комбинации при n=6. 100110 Код имеет кодовое расстояние d=2 и применяется для обнаружения ошибок. Корректирующая способность кода: код позволяет обнаруживать ошибки любой кратности, за исключением, одновременного искажения поверочного и информационного в парах (a1и b1; a2 и b2; a3 и b3; a1b1 и a2b2 и т.п.).

Процедура обнаружения Процедура обнаружения состоит в сравнении символов в парах и формирование по этим проверкам синдрома ошибки S = SrSr-1…S1….S1. Si = 0 (i = r÷1), если значение символов в парах разное; S=1, если значение символов в парах одинаковое. Значение Si находится как результат сложения по модулю два символов в паре, причем проверочный символ берется в инверсном виде.

Процедура обнаружения Процедура обнаружения состоит в сравнении символов в парах и формирование по этим проверкам синдрома ошибки S = SrSr-1…S1….S1. Si = 0 (i = r÷1), если значение символов в парах разное; S=1, если значение символов в парах одинаковое. Значение Si находится как результат сложения по модулю два символов в паре, причем проверочный символ берется в инверсном виде. Где значение i-ых информационных и поверочных символов в принятой кодовой комбинации,

Относительная скорость передачи находится по формуле q = k / n, а избыточность кода И = (n – k ) / k Корректирующая способность кода проявляется в том, что код обнаруживает все ошибки за исключением одновременного искажения символов в парах a1 и b1, a2 и b2, a3 и b3, a1 b1 и a2 b2, a1 b1 и a3 b3, a2 b2 и a3 b3 Процедура обнаружения и формирования синдрома ошибки рассмотрена на следующих примерах:

Процедура обнаружения и формирования синдрома ошибки 1) передавалась комбинация 100110. В процессе передачи искажен первый символ, вектор ошибки e=100000. Принята комбинация 000110. Находится синдром ошибки S = S3 S2 S1 Откуда S =001 Синдром не нулевой, ошибка есть и она обнаружена.

Ошибка есть, но она не обнаружена 2) передавалась комбинация Vi = 100110. В процессе передачи искажены третий и четвертый символы. Вектор ошибки еi = 001100. Принята комбинация Vi* = 101010. Находится синдром ошибки S=S3 S2 S1. Синдром S=000. Ошибка есть, но она не обнаружена.

Вероятность появления ошибочной комбинации Вероятность появления ошибочной комбинации на выходе устройства обнаружения ошибок при одноразовой передаче комбинации по двоичному симметричному каналу (ДСК) равна вероятность необнаружения ошибки Рн (равна вероятности одновременного искажения информационных и проверочных символов в парах (одной, двух, и т.д. до k-той)) и определяется по формуле где р – вероятность искажения одного символа, q=1-p – вероятность правильного приема одного символа

КОД С ПОСТОЯННЫМ ВЕСОМ Этот код является неразделимым, не систематическим, циклическим, нелинейным кодом длины n. Код имеет постоянное число единиц l и нулей m в кодовых комбинациях, характеризуется эквивалентным числом kэ информационных и rэ проверочных символов. kэ + rэ = n. N – количество комбинаций кода. Длина кода n определяется путем подбор а при использовании соотношения Обычно В этом случае имеем наибольшее число сочетаний. Код имеет d = 2 и применяется для обнаружения ошибки.

Процедура построения: используя соотношение N ≤ Cnl . Методом подбора для заданного N определяем n и l . Из всех комбинаций N0=2n выбираем комбинации, содержащие l единиц. Затем строим кодовые комбинации – Vi=a1a2a3…an., Корректирующая способность кода: код обнаруживает все ошибки за исключением одновременного перехода 1 в 0 и такого же количества переходов 0 в 1. В этом случае число 1 остается равным l и такие ошибки не обнаруживаются. Процедура обнаружения состоит в подсчете числа единиц в кодовой комбинации. Результаты проверки характеризуются одним символом синдрома S = S1. S1 = 0, если число единиц nℓ в принятой кодовой комбинации равно l (nl = l), то считается, что ошибки нет или ошибка есть, но она не обнаруживается. Здесь осуществляется обычно сложение (не по модулю два), nl = a1*+ a2* + a3* +…+ an*, a1*, a2* ….. an* - символы искаженной кодовой комбинации.

Вероятность появления ошибочной комбинации S1 =1, если число единиц nl принятой кодовой комбинации неравно то ошибка есть и она обнаруживается. Относительная скорость передачи q и избыточность кода И определяются формулами: И Вероятность появления ошибочной комбинации на выходе устройства обнаружения ошибок при одноразовой передаче комбинации по двоичному симметричному каналу (ДСК) равна вероятности искажения одной единицы и одного нуля, дух единиц и двух нулей и т.д. где q = 1 – p – вероятность правильного приема одного символа, p – вероятность искажения одного символа.

ЛИНЕЙНЫЕ (n,k)-КОДЫ В классе блоковых разделимых корректирующих кодов различают коды систематические и несистематические. Систематическим называют такой код, в комбинациях которого информационные символы занимают первые k позиций, а проверочные – последние r = n – k позиций. Если информационные символы обозначать через ai (i = 1 ÷ k), а проверочные – через bj (j = 1 ÷ r), то любая комбинация V систематического кода, согласно определению, должна иметь структуру V = (a1a2 … akb1b2 … br) При ином расположении информационных и проверочных символов код называется несистематическим. Остановимся на рассмотрении систематических линейных кодов в рамках теории линейных зависимостей.

Систематический линейный код Двоичный (n,k) – код называется линейным, если его проверочные символы bj (j = 1 ÷ r) находятся как суммы по mod2 определенных информационных символов ai (i = 1 ÷ k). Где – символ суммирования по mod2. Cji – коэффициенты, могущие принимать значения либо 0, либо 1. Операция сложения по mod2 является линейной операцией, отсюда и название кода. Если проверочные символы определяются по другому правилу, то (n,k)-код называется нелинейным.

Закон построения линейного кода Закон построения линейного кода задается совокупностью коэффициентов Cji, число которых k×r .

Линейный систематический код Построить линейный систематический (7,4)-код, заданный следующей совокупностью коэффициентов Cji (всего таких коэффициентов должно быть задано 4·3=12): i=(1÷4), j=(1÷3)

Проверочные символы находятся по формулам:

Строим первичный код с числом комбинаций N=2k = 16 и записываем его в таблицу графы 2,3, 4,5. По приведенным формулам определяются проверочные символы и записываются в графы 6,7,8 таблицы. В графу 8 записывается вес полученных кодовых комбинаций. Например, первичная комбинация a1a2a3a4 = 1001, b1 = a1a2a4 = 101=0, b2 = a1a3a4 = 101=0, b3=a2a3a4=001=1. Корректирующий код 1001001. Вес этой комбинации w=3. Комбинация 9

Таблица 1

Для другой совокупности коэффициентов Cji был бы получен другой линейный код с тем же или иным d. Отметим два интересных свойства линейных кодов. 1.Сумма по mod2 любых двух комбинаций линейного кода снова дает комбинацию этого же кода. В справедливости этого легко убедиться, сложив любые две комбинации. 2.Кодовое расстояние d линейного кода равно минимальному весу его ненулевых комбинаций. Построив код и проставив справа веса всех комбинаций, можно убедиться, что d = wmin=3. Это свойство дает очень простой способ определения кодового расстояния для любого линейного (n,k)-кода.

Характеристики систематического (n,k)-кода на примере (7,4)-кода с совокупностью коэффициентов Cji, приведенных выше, n = 7, k = 4, r = n −k = 3. 1. Код разделимый, длина кода – n. 2. Число информационных символов k=4 , число проверочных символов r = n – k=7– 4 = 3. 3. Кодовое расстояние d, равно минимальному весу его ненулевых комбинаций d = 3. 4. Избыточность кода И=(n-k)/k 5. Относительная скорость передачи q = k / n. 6. Корректирующая способность кода. Код обнаруживает все однократные и двукратные ошибки и некоторые ошибки большей кратности. Код исправляет однократные ошибки. 7. Процедура обнаружения и исправления ошибок. Обнаружение ошибок в комбинациях линейных кодов. Пусть передана комбинация V=(a1a2…akb1b2…br), а принята комбинация V*=(a1*a2*…ak*b1*b2*…br*). В общем случае из-за возможных искажений не все одноименные символы этих комбинаций совпадают.

По принятым информационным символам на приемной стороне вычисляются проверочные: По принятым информационным символам на приемной стороне вычисляются проверочные: Вычисленные значения сравниваются с принимаемыми символами bj*. Это сравнение можно осуществить путем операции сложения по mod2 Результаты сравнения можно представить в виде набора из r символов (SrSr–1…S2S1) . Ясно, что если для всех j сравнение показало совпадение вычисленного и полученного проверочного символа (bj**= bj*), то это свидетельствует об отсутствии искажений в принятой комбинации. Иными словами, если r – элементная комбинация (Sr … Sr S1) состоит из одних нулей, то ошибки нет; если хотя бы один символ в этом наборе принял значение 1, то это говорит о наличии ошибок в принятой комбинации. Поэтому набор символов S=(Sr … S1) называют синдромом или опознавателем ошибок.

Пусть была передана комбинация кода Vi=1001001, а принята Vi* = 1001011, Vi* = a1*a2*a3*a4*b1*b2*b3*. Пусть была передана комбинация кода Vi=1001001, а принята Vi* = 1001011, Vi* = a1*a2*a3*a4*b1*b2*b3*. Тогда Сравнение вычислительных символов с принятыми проверочными дает: Т.е. получен ненулевой синдром S = 010, что свидетельствует об ошибке в принятой комбинации.

Процесс исправления ошибок осуществляется аналогичным способом. Полученный ненулевой синдром, в виде трехзначного двоичного кода указывает позицию, на которой произошла ошибка. Исправление ошибки заключается в замене принятого значения символа на инверсный (0 на 1 или 1 на 0). Процесс исправления ошибок осуществляется аналогичным способом. Полученный ненулевой синдром, в виде трехзначного двоичного кода указывает позицию, на которой произошла ошибка. Исправление ошибки заключается в замене принятого значения символа на инверсный (0 на 1 или 1 на 0). Верность передачи определяется как вероятность обнаружения ошибки, при использовании (n,k)-кода в качестве обнаруживающего ошибку, или как вероятность исправления одиночной ошибки, при использовании (n,k)-кода в качестве исправления одиночной ошибки.

ЛИНЕЙНЫЙ НЕ СИСТЕМАТИЧЕКИЙ КОД (КОД ХЭМММИНГА НЕ СИСТЕМАТИЧЕСКИЙ) Этот код является разделимым не систематическим линейным кодом длины n с k информационными и r проверочными символами, обозначается как (n,k)-код. (7,4)- код Хэммминга позволяет обнаруживать одиночные и двойные ошибки и ряд ошибок большей кратности или исправлять одиночную ошибку. Построение корректирующего кода. В качестве первичного (исходного) берется двоичный код на все сочетания с числом информационных символов k, к которому добавляется проверочные символы r , общая длина комбинации кода n = k + r.

Определение числа контрольных символов. Для этого можно воспользоваться следующими рассуждениями. При передаче по каналу с шумами может быть или искажен любой из n символов кода, или слово передано без искажений. Таким образом, может быть n+1 вариант искажения (включая передачу без искажений). Используя контрольные символы, необходимо различить все n+1 вариантов. С помощью контрольных символов r можно описать 2r событий. Значит, должно быть выполнено условие: 2r ≥ n +1 = k + r +1 В таблице представлена зависимость между n, k и r полученная из этого неравенства.

Число проверочных символов r в коде Хэмминга в зависимости от числа информационных символов k

Размещение проверочных символов В принципе место расположения проверочных символов может быть произвольным. Однако, произвольное расположение проверочных символов затрудняет проверку принятого кода. Для удобства обнаружения искаженного символа и его исправления целесообразно размещать их на местах, определяемых по значению 2i (i = 0 ÷ n–1), т.е. на позициях 1,2,4,8, и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для семиэлементной закодированной комбинации можно записать b1b2a1b3a2a3a4. Значения информационных символов a1a2a3a4 определяется первичным двоичным кодом на все сочетания. Первичный код имеет 2k=N комбинаций. Значения проверочных символов в коде определяются из выражения: b1=a1Åa2Åa4, b2=a1Åa3Åa4, b3=a2Åa3Åa4

Пример построения комбинации корректирующего кода. Пример построения комбинации корректирующего кода. Пусть комбинация первичного кода будет 1001 тогда: a1=1, a2 =0, a3=0, a4=1. Значения проверочных символов: b1=a1Åa2Åa4= 1Å0Å1=0 b2=a1Åa3Åa4 =1Å0Å1=0 b3=a2Åa3Åa4=0Å0Å1=1 Комбинация корректирующего кода будет иметь вид: b1 b2a1 b3a2a3a4=001001

Характеристики не систематического (n,k)-кода на примере (7,4)-кода. Характеристики не систематического (n,k)-кода на примере (7,4)-кода. Код разделимый, длины кода – n Число информационных символов k, число поверочных символов r = n – k Кодовое расстояние d, равно минимальному весу его ненулевых комбинаций Избыточность кода И =(n – k) / k Корректирующая способность кода. Код обнаруживает все однократные и двухкратные ошибки и некоторые ошибки большей кратности. Код исправляет однократные ошибки.

Обнаружение ошибок Обнаружение ошибки сводится к проверке выполнения соотношений и нахождению синдрома ошибки для каждой принимаемой комбинации: При исправлении ошибки по тем же правилам находится синдром. Синдром представляет собой r - разрядное двоичное число, указывающее позицию искаженного символа S=S3 S 2S1,

Пример: Передаваемая комбинация =0011001. Искажен четвертый символ, тогда принятая комбинация: 0010001=b1*b2*a1* b3*a2*a3*a4* Синдром определяется в соответствии с формулами: S1=a1*Åa2*Åa4*Åb1*=1Å0Å1Å0=0, S2=a1*Åa3*Åa4*Åb2*=1Å0Å1Å0=0, S3=a2*Åa3*Åa4*Åb3*=0Å0Å1Å0=1 S=S3 S 2S1=100. Двоичное число 100 указывает на искажение 4-го символа. После замены значения четвертого символа на инверсный получается исходная комбинация 0011001. В приведенной ниже таблице указан синдром и соответствующий ему искаженный символ, который обнаруживается и исправляется.

Вероятность передачи Вероятность передачи определяется как вероятность обнаружения ошибки при использовании (n,k)-кода в качестве обнаруживаемого ошибку или как вероятность исправления одиночной ошибки при использовании (n,k)-кода в качестве исправляющего одиночную ошибку.