Циклический код - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Циклический код. Доклад-сообщение содержит 89 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Циклические коды незаменимы при передаче информации в каналах связи, в которых отсутствует возможность повторной передачи данных Циклические коды применяются: при записи и считывании на HDD, CD и DVD, при использовании USB-портов для обмена информацией, при передаче аудио и видео информации.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Любые «k» строк этой матрицы линейно независимы и могут служить основой для получения любой разрешенной кодовой комбинации циклического кода. Любые «k» строк этой матрицы линейно независимы и могут служить основой для получения любой разрешенной кодовой комбинации циклического кода. Число возможных циклических кодов существенно меньше числа групповых кодов.

Слайд 7

Описание слайда:

В циклическом коде кодовые комбинации удобно записывать в виде многочлена (n – 1) степени относительно фиктивной переменной x. В циклическом коде кодовые комбинации удобно записывать в виде многочлена (n – 1) степени относительно фиктивной переменной x. Показатель степени при x соответствует номеру разряда, уменьшенному на единицу. Младший разряд соответствует x0 = 1. Коэффициенты при x имеют значения 0 или 1.

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Посмотрим, делится ли полученный многочлен на

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Для обнаружения ошибок в циклических кодах принятую кодовую комбинацию делят на образующий многочлен. Если остаток от деления R(x) = 0, то принимается решение, что ошибок нет. Если R(x) ≠ 0, то были ошибки. Вектор ошибок определяется по виду остатка.

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Циклический код Математическое введение

Слайд 14

Описание слайда:

Разрешенную кодовую комбинацию Ц.К. можно рассматривать как элемент подмножества множества многочленов степени не выше (n – 1). Для анализа Ц.К. используется аппарат теории колец. Коммутативным кольцом называется множество, в котором определены две операции: сложение и умножение. Обе коммутативны

Слайд 15

Описание слайда:

Обе коммутативны ассоциативны, то есть; и связаны законом дистрибутивности:

Слайд 16

Описание слайда:

Правила выполнения операций Нужно чтобы замкнутое множество многочленов (n – 1) степени образовало кольцо

Слайд 17

Описание слайда:

Правило 1. Сложение В качестве операции сложения выберем сложение по модулю два без переноса в старший разряд

Слайд 18

Описание слайда:

Правило 2. Умножение Операция умножения по обычным правилам не проходит, так как нарушается условие замкнутости: Введем операцию символического умножения по следующим правилам: Умножение выполняется по обычным правилам с приведением подобных членов путем сложения по модулю два; если полученный многочлен имеет степень меньше чем (n – 1), то он и принимается за результат умножения, если же степень больше чем (n – 1), то он делится на двучлен c записью в качестве результата умножения остатка от деления.

Слайд 19

Описание слайда:

Пример: Сдвиг с переносом единицы из старшего разряда в младший Имеем: После сдвига, соответствующего умножению на x, получим: , что недопустимо, так как x7 имеет степень более разрешенной xn–1, в данном случае соответствует x6. Поделим на многочлен

Слайд 20

Описание слайда:

Поделим на многочлен Получим в остатке R(x): В качестве результата умножения принимаем R(x), что соответствует переносу единицы из старшего разряда в младший.

Слайд 21

Описание слайда:

ИДЕАЛ При выбранных операциях и все множество многочленов степенью ≤ (n – 1) образуют кольцо. Подмножество многочленов в кольце, кратных образующему многочлену g(x), называется идеалом, порождаемым g(x).

Слайд 22

Описание слайда:

Количество элементов в идеале зависит от вида g(x) Если g(x) = 0, то в идеале всего один элемент «0». Если g(x) = 1, то в идеал входят все элементы кольца. Если g(x) многочлен степени m = n – k, то число элементов в идеале – 2k. Эти элементы и есть искомый нами Ц.К. Построение Ц.К. сводится к выбору образующего многочлена g(x) с заданными корректирующими способностями

Слайд 23

Описание слайда:

Циклический код Требования к образующему многочлену

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

поэтому i-тую строку матрицы ƒi(x) можно записать: где c = 1, если максимальная степень многочлена больше (n – 1); c = 0, если имеет степень < n.

Слайд 26

Описание слайда:

делится на g(x) без остатка. делится на g(x) без остатка. Поэтому, чтобы ƒi(x) делилось на g(x) без остатка, необходимо, чтобы делилось на g(x) тоже без остатка.

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

Наибольшее число остатков дает неприводимый многочлен степени «m», когда m; n и k связаны между собой условиями: Наибольшее число остатков дает неприводимый многочлен степени «m», когда m; n и k связаны между собой условиями: m = n – k, а n = 2m – 1.

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

Принятую искаженную кодовую комбинацию можно представить как: где ЗККi+j – запрещенная (искаженная) кодовая комбинация; ƒi(x) – i-тая разрешенная кодовая комбинация; – вектор ошибки в j-том разряде, то есть X j. Ошибка обнаруживается, если при делении ЗККi+j на g(x) образуется остаток. Но ƒi(x) делится на g(x) без остатка. Поэтому нужно выбрать такой многочлен g(x), чтобы при делении на g(x) получился остаток.

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

Выбираем многочлен g(x), чтобы при делении на g(x) получился остаток Таким многочленом является многочлен , который при делении всех элементов кольца на него дает два случая: R(x) = 0, то есть элемент кода принадлежит идеалу; R(x) = 1, то есть элемент кода имеет ошибку. Вектор ошибки X j имеет единицу в одном из разрядов.

Слайд 33

Описание слайда:

Например, для кода (7; 4) ошибка в четвертом разряде имеет вид 0001000. При делении X j на всегда получаем остаток R(x) = 1.

Слайд 34

Описание слайда:

Обратим внимание, что для обнаружения одиночной ошибки дистанция между двумя Р.К.К. должна быть не менее, чем в 2 символа, так как d ≥ r + 1 = 1 + 1 = 2 и в принятом нами тоже 2 символа. g(x) выбираем из таблицы многочленов, не приводимых над полем по условию d = 2. Таких многочленов всего один

Слайд 35

Описание слайда:

во многих случаях целесообразно пользоваться таблицей наилучших двоичных циклических кодов, предлагаемой ITU (International Telecommunication Union)

Слайд 36

Описание слайда:

Из соотношения (2n–k – 1) ≥ числа ошибок, которые мы хотим обнаруживать. Из соотношения (2n–k – 1) ≥ числа ошибок, которые мы хотим обнаруживать. Так как мы обнаруживаем лишь факт есть ошибка (в любом разряде) или ее нет, то неравенство можно записать так: 2n–k – 1 ≥ 1, то есть, 2n–k ≥ 2, то есть n – k = 1; n = k + 1. Это соответствует одному дополнительному разряду, который следует заполнить нулем или единицей, так, чтобы полученная Р.К.К. делилась без остатка

Слайд 37

Описание слайда:

.К.К. будет делится на без остатка, если в ней будет четное число единиц. Убедимся в этом. .К.К. будет делится на без остатка, если в ней будет четное число единиц. Убедимся в этом. Пусть k = 7. Имеем К.К. Дополним ее поверочным разрядом: так как в информационных разрядах всего 3 единицы, то в поверочном разряде должна быть записана единица, чтобы полученная Р.К.К. делилась без остатка.

Слайд 38

Описание слайда:

Где ее записывать, вначале К.К. или в конце значения не имеет Поделим РКК на

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

Неприводимые многочлены

Слайд 41

Описание слайда:

Еще таблица

Слайд 42

Описание слайда:

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

Слайд 43

Описание слайда:

Для исправления одиночных ошибок в n разрядной К.К. необходимо определить, какой разряд был искажен. Поэтому каждому вектору ошибки необходимо сопоставить свой остаток. Для исправления одиночных ошибок в n разрядной К.К. необходимо определить, какой разряд был искажен. Поэтому каждому вектору ошибки необходимо сопоставить свой остаток. Для исправления одиночной ошибки должно быть выполнено условие: 2n – k – 1 = 2m – 1 ≥ Cn1 = n, то есть 2m ≥ n + 1;

Слайд 44

Описание слайда:

Из последнего равенства определяется число проверочных разрядов – это целое число с округлением log2(n + 1) в большую сторону. Из последнего равенства определяется число проверочных разрядов – это целое число с округлением log2(n + 1) в большую сторону. В теории кодирования доказано, что если m и n связаны условием n = 2m – 1, то многочлен может быть представлен произведением всех без исключения неприводимых многочленов степени которых являются делителями числа «m» от единицы до «m». Причем всегда имеется хотя бы один многочлен степени «m».

Слайд 45

Описание слайда:

Для исправления одиночных ошибок минимальная дистанция между двумя Р.К.К. должна быть: Для исправления одиночных ошибок минимальная дистанция между двумя Р.К.К. должна быть: d ≥ 2S + 1 = 2·1 + 1 = 3. Таким образом, нам потребуется выбрать g(x), удовлетворяющий двум условиям: и d = 3, где m – максимальная степень образующего многочлена, а d – количество значащих членов в нем.

Слайд 46

Описание слайда:

Например: Пусть n = 15; S = 1; тогда 2n – k – 1 ≥ n, откуда k = 11 и m = n – k = 15 – 11 = 4 или Делителями числа «m» являются: 1; 2; 4. Разложим на сомножители:

Слайд 47

Описание слайда:

Нас интересуют неприводимые многочлены степени m = 4. Таких многочленов в разложении – три. Проверим, дают ли они n = 15 различных остатков, чтобы поставить им в соответствие ошибки в различных разрядах. Пусть g(x) = х4 + х3 + 1 Остатки будем получать путем деления X j на g(x).

Слайд 48

Описание слайда:

Векторы ошибок младших разрядов имеют вид:

Слайд 49

Описание слайда:

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

Слайд 50

Описание слайда:

Однако использовать для тех же целей многочлен Однако использовать для тех же целей многочлен x4 + х3 + х2 + x + 1 нельзя. При проверке числа различных остатков обнаруживается, что их у него не 15, а только 5 Это объясняется тем, что многочлен x4 + х3 + х2 + x + 1 входит в разложение не только двучлена x15 + 1, но и двучлена х5 + 1.

Слайд 51

Описание слайда:

Из приведенного примера следует, что в качестве образующего следует выбирать такой неприводимый многочлен g(x), который, являясь делителем двучлена хn+1, не входит в разложение ни одного двучлена типа x^ λ+1, степень которого λ меньше n В этом случае говорят, что многочлен q(x) принадлежит показателю степени n.

Слайд 52

Описание слайда:

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

Слайд 53

Описание слайда:

Вектор двойных ошибок можно записать: где λ = i – j > 0, а i > j.

Слайд 54

Описание слайда:

Для того, чтобы обнаруживать двойные ошибки, необходимо, чтобы при делении ei+j(x) на g(x) мы имели остаток. Для того, чтобы обнаруживать двойные ошибки, необходимо, чтобы при делении ei+j(x) на g(x) мы имели остаток. Но это условие всегда выполняется, если в качестве g(x) взять многочлен, предназначенный для исправления одиночных ошибок, так как он не кратен X j и не входит в разложение (xλ 1), если λ < n.

Слайд 55

Описание слайда:

Для обнаружения двойных ошибок (R = 2), необходимо, Для обнаружения двойных ошибок (R = 2), необходимо, чтобы минимальная дистанция между Р.К.К. была d ≥ R + 1 = 2 + 1 = 3, что соответствует исправлению одиночной ошибки d ≥ 2S + 1 = 2 · 1 + 1 = 3.

Слайд 56

Описание слайда:

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

Слайд 57

Описание слайда:

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

Слайд 58

Описание слайда:

Если известен образующий многочлен g(x) степени m, обнаруживающий ошибки кратности до R включительно в n-разрядном коде, Если известен образующий многочлен g(x) степени m, обнаруживающий ошибки кратности до R включительно в n-разрядном коде, то образующий многочлен, обнаруживающий ошибки кратности до (R + 1) получается следующим образом:

Слайд 59

Описание слайда:

Например: n = 15; k = 11; m = 4; g(x) = x4 +x3 +1 – исправляет одиночные ошибки. Значит, он может обнаруживать и двойные ошибки. Нужно построить код, который может обнаруживать тройные ошибки.

Слайд 60

Описание слайда:

Это эквивалентно добавлению еще одного проверочного разряда, то есть при k = 11; m = 4 + 1 = 5 и n = k + m = 16.

Слайд 61

Описание слайда:

Но возможно и другое решение: Но возможно и другое решение: n оставляется равным 15, а так как m = 5, то k получается равным 10

Слайд 62

Описание слайда:

Чтобы построить код, обнаруживающий ошибки произвольной кратности R следует : Найти многочлен g(x), обнаруживающий ошибки кратности (R – 1). Помножить этот многочлен на (x 1), что эквивалентно добавлению еще одного проверочного разряда, и получить новый g1(x). При фиксированном k, увеличивается число проверочных разрядов m; а при фиксированном n – уменьшается число информационных разрядов кода. Необходимо убедиться, что полученный код способен исправлять ошибки во всех разрядах кодовой комбинации.

Слайд 63

Описание слайда:

Методы построения циклического кода

Слайд 64

Описание слайда:

Зная кодовую комбинацию из «k» информационных символов – ai(x) и образующий многочлен – g(x), нужно получить разрешенные кодовые комбинации (Р.К.К.) – ƒi(x). Зная кодовую комбинацию из «k» информационных символов – ai(x) и образующий многочлен – g(x), нужно получить разрешенные кодовые комбинации (Р.К.К.) – ƒi(x). Существуют три метода образования Р.К.К. циклического кода: Методом умножения Методом деления Методом группового кода

Слайд 65

Описание слайда:

Методы построения циклического кода методом умножения

Слайд 66

Описание слайда:

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

Слайд 67

Описание слайда:

Пример Пусть имеем код (7; 4), то есть код исправляющий одиночные ошибки. Пусть g(x) = x3 x 1. Необходимо передать ai(x) = 1011.

Слайд 68

Описание слайда:

Для получения Р.К.К. –умножим и получим ƒi(x)

Слайд 69

Описание слайда:

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

Слайд 70

Описание слайда:

На приемной стороне, чтобы судить есть ошибка или нет, необходимо принятую кодовую комбинацию (К.К.) поделить на g(x). На приемной стороне, чтобы судить есть ошибка или нет, необходимо принятую кодовую комбинацию (К.К.) поделить на g(x). Если ошибок нет, то остаток от деления r(x) должен быть равен нулю. Делим:

Слайд 71

Описание слайда:

Получили остаток, отличный от нуля. Получили остаток, отличный от нуля. По нему мы должны определить, в каком разряде имеет место ошибка. Для этого необходимо определить, какой остаток ri(x) даст единичная ошибка в i-том разряде.

Слайд 72

Описание слайда:

До ошибки в четвертом разряде остаток соответствует самой ошибке, а начиная с ошибки в 4-ом разряде происходит деление.

Слайд 73

Описание слайда:

В примере остаток , то есть ошибка в пятом разряде. Исправим ошибку:

Слайд 74

Описание слайда:

Но, получив ƒi(x), мы не получили ai(x), то есть снова приходится делить ƒi(x) на g(x):

Слайд 75

Описание слайда:

Методы построения циклического кода методом деления

Слайд 76

Описание слайда:

Чтобы получить разделимый код : ai(x) умножают на xm что эквивалентно дописыванию к ai(x) справа m нулей. Полученный многочлен делится на g(x). В результате получается частное от деления g(x) и остаток r(x).

Слайд 77

Описание слайда:

Разрешенная кодовая комбинация ƒi(x) получается путем сложения и r(x)

Слайд 78

Описание слайда:

Степень многочлена g(x) – m, а степень остатка – (m – 1). Поэтому сложение эквивалентно приписыванию остатка r(x) к ai(x), так как m разрядов в – нулевые. В то же время ƒi(x) делится на g(x) без остатка так как: Данная методика используется при k > m.

Слайд 79

Описание слайда:

Пример (тот же) ai(x) = 1011; g(x) = 1011. Так получилось потому, что ai(x) совпало с g(x).

Слайд 80

Описание слайда:

Если в линии связи произошла ошибка в пятом разряде , то будем иметь Поделим на g(x) и получим остаток r(x)

Слайд 81

Описание слайда:

Исправим принятую К.К.: И сразу получаем ai(x) как первые k символов, то есть 1011.

Слайд 82

Описание слайда:

Методы построения циклического кода По методу группового кода

Слайд 83

Описание слайда:

Ц.К. является разновидностью группового кода (Г.К.), Ц.К. является разновидностью группового кода (Г.К.), а в Г.К. проверочные символы определяются как комбинация информационных. Для определения проверочных символов воспользуемся рекуррентным соотношением:

Слайд 84

Описание слайда:

Зная значения информационных разрядов a0 (старший разряд); a1; a2;... ak–1 можно получить значения проверочных разрядов ak; ak+1;... an–1 Зная значения информационных разрядов a0 (старший разряд); a1; a2;... ak–1 можно получить значения проверочных разрядов ak; ak+1;... an–1 Получается код, полностью совпадающий с кодом, полученным делением. Метод применяется при m > k и k = n – m, если n = 2m – 1.

Слайд 85

Описание слайда:

Реализация кодирующих устройств циклического кода методом умножения

Слайд 86

Описание слайда:

Нарисуем схему умножения образующего многочлена g(x) на любой многочлен ai(x). Нарисуем схему умножения образующего многочлена g(x) на любой многочлен ai(x). В схеме умножения имеется m ячеек памяти в соответствии со степенью многочлена g(x). Ячейка x0 не нужна, а потому показана пунктиром.

Слайд 87

Описание слайда:

Входной сигнал подается в ячейки памяти слева, начиная со старших разрядов. Входной сигнал по тактам продвигается по ячейкам памяти в соответствии с частотой генератора тактовых импульсов (ГТИ). За один такт продвигается вправо содержание всех ячеек памяти одновременно. На выходной сумматор по модулю два поступают синхронно те нули и единицы, которые идут в соответствующие ячейки памяти.

Слайд 88

Описание слайда:

В нашем случае это x3; x1 и x0, В нашем случае это x3; x1 и x0, то есть ячейки, соответствующие наличию единицы в записи g(x) = 1011 = x3 x 1. Сигнал, поступающий в ячейку x2, на сумматор не идет.