Вернер М. Основы кодирования (2004) (1151882), страница 20
Текст из файла (страница 20)
В спутниковой связи, например, чащевсего пользуются энергетическим критерием. Сущность его в следующем: так как спутниковые линии связи близки к каналам с АБГШ,вначале находится SNR на бит передаваемой информации, обеспечивающее заданную вероятность битовой ошибки Рь при передаче безкодирования.Аналогичное SNR на кодовый символ подсчитываете для передачи с кодированием при условии BER = Рь, где Рь задано. Послеэтого, находится SNR на бит полезной информации с учетом скорости кода.
Разность энергетических затрат на бит передаваемой информации при передаче без кодирования и с кодированием называется энергетическим выигрышем кода (ЭВК).Замечание. Использование кодов большой длины с довольно сложной алгебраической структурой в современных спутниковых линияхсвязи позволяет достичь ЭВК — 6 - 8 дБ при Рь = 10~5. Заметим,что при снижении Рь ЭВК возрастает.2.4-4- Коды ХэммингаКоды Хэмминга образуют важное семейство простейших линейныхблоковых кодов.
Для каждого натурального т > 3 существует двоичный код Хэмминга со следующими параметрами:Коды Хэмминга.• длина кодовых слов п = 2т — 12-4- Свойства линейных блоковых кодов I49J• число информационных разрядов к = 1т — 1 - т• число проверочных разрядов т = п — к• корректирующая способность t = l,d m j n = 3• совершенные коды у/Конструкция кодов Хэмминга определяется следующими свойствами проверочной матрицы вида (2.15).Так как минимальное расстояние кода Хэмминга d m i n = 3, всестолбцы проверочной матрицы должны быть попарно различными (проверочная матрица не должна содержать одинаковыхстолбцов).• Из d m i n = 3 следует также, что каждая строка порождающейматрицы должна содержать как минимум три единицы, таккак строки порождающей матрицы в свою очередь являютсякодовыми словами. Если порождающая матрица представленав виде (2.14), то это значит, что строки матрицы Р должнысодержать как минимум две единицы.
(Следовательно, это относится и к столбцам транспонированной матрицы РТ)• Рассмотрим проверочную матрицу. Согласно (2.8), она имееттвид H ( n _ f c ) x n = (In-fcPL(n-fc))- Матрица Р содержит А; столбцов и т = п — к строк. Используя двоичные символы «О» и «1»,можно образовать 2т различных столбцов. Но, так как ранеебыло сказано, что каждый столбец должен содержать как минимум две единицы, то следует отбросить один нулевой столбеци т столбцов, содержащих по одной единице. Таким образом,ттостается 2 — т — 1 возможностей.
Так как 2 — тп — 1 = кч маттрица Р содержит ровно к столбцов, то все эти возможностииспользованы. Отсюда следует, что столбцы транспонированной матрицы Р т представляют собой все возможные двоичныеГлава 2. Линейные блоковые коды4слова длины тп = п — к, содержащие не менее двух единиц.Пример: (15,11)-код Хэмминга.На примере (15,11)-кода Хэминга можно наглядно пояснить всеперечисленные выше особенности конструкции:1 0 0 0Н 4x150 1 0 00 0 1 01 0 0 111000110001110100 11 00 01 111100111101111011111\. (2.40)—у14Вес Хэмминга u« =2шк=3шд=4По проверочной матрице с помощью (2.15) и (2.14) строится порождающая матрица/11001 0 0 0 0 0 0 0 0 0 0 \0 1 1 0 0 1 0 0 0 0 0 0 0 0 00011001000000001 0 1 1 0 0 0 10 0 0 0 0 0 00101000010000001 0 0 1 0 0 0 0 0 1 0 0 0 0 0.1 1 1 0 0 0 0 0 0 0 1 0 0 0 0-01 1 1 О 0 0 0 0 0 0 1 0 0 01011000000001001101000000000101111 00000000001(2.41)PllПример: Передача данных с использованием (15,11)-кода Хэмминга.4Отметим, что п столбцов матрицы H m X n = ( I n - k P ^ X ( n _ t ) ) содержат все возможные двоичные слова длины га, за исключением нулевого, т.е.
п = 2 т — 1 ивсе столбцы различны. Такое представление позволяет сразу же раскрыть методкоррекции одиночных ошибок. В самом деле, уравнение синдромного декодирования (2.19) имеет вид s = е 0 Н т . Если е - вектор одиночной ошибки, то онсодержит только одну единицу в г-ом ошибочном разряде кодового слова. В этомслучае синдром (вектор s) представляет собой г-ый столбец матрицы Н. Так каквсе столбцы матрицы Н различны, то п возможным позициям одиночной ошибки в кодовом слове соответствуют в точности п различных синдромов, поэтому,по значению синдрома s можно однозначно определить номер разряда кодовогослова, в котором произошла одиночная ошибка, т.е.
ее исправить. - Прим. перев.2.4- Свойства линейных блоковых кодов 151В данном примере мы сравниваем результаты использования дляпередачи данных (15,П)-кода Хэмминга с ранее полученными результатами для (7,4)-кода Хэмминга. Скорость (15,11)-кода существенно выше (7,4)-кода, так как Д(15,ц) = 15/11 « 0,73, а Д(7,4) =4/7 « 0,57. Посмотрим, как изменятся другие параметры кодирования. Для этого выполним задания Д.
2. 3. из предыдущего примера.Решение.1. Кодовое слово будет принято правильно, если все его разрядыбудут приняты без ошибок, таким образомРс = (1 - Р е ) 1 5 -(2.42)Для вероятности ошибки на двоичный символ Ре = 0,023, взятой изпредыдущего примера (2.32), имеемРс = (1 - 0,023) 15 « 0,705.(2.43)2.
Вероятность необнаружимой ошибки получим из оцейки (2.30)(2* - l)/^ m i ° ж 2047 • 0,0233 « 0,025.(2.44)3. При скорости передачи двоичных символов 16 кбит/сек, эффективная скорость передачи данных составляетitnn11 -0,705 -16 кбит/сек^.,nlp,Rb,ef/ = -PcRb ~7Z« 8,27 кбит/сек. (2.45)В приведенных расчетах мы исходили из одной и той же вероятностиошибки двоичного символа Ре = 0,023 для (15,11)- и (7,4)-кодов.Проведем аналогичные расчеты при одинаковой мощности передатчика. В этом случае, потери энергетики на один символ по сравнению с передачей без кодирования составляют для (15,11)-кода только15101og2 —- ~ 1,4 д Б (для (7,4)-кода эта величина составляет 2,4 д Б- см.
предыдущий пример). Таким образом, отношению сигнал/шумравному 7 д Б соответствует вероятность ошибки двоичного символа,равная 0,013, поэтомуРс = (1-0,013)15!«0,82,(2.46)и вероятность необнаружения ошибки оценивается сверху как(2* - 1)Р*""" « 2047 • 0,013 3 и 0,0045.(2.47)152Глава 2. Линейные блоковые кодыЭффективная скорость передачи также возрастаетк11 0,82 • 16 кбит/секRb,e./f = -РсЯъ «•jg« 9,62кбит/сек.(2.48)Условие неизменной мощности передатчика более близко к практике,чем условие равенства вероятностей ошибки двоичных символов. Посравнению с (7,4)-кодом, для (15,11)-кода мы получаем некоторыйвыигрыш по эффективной скорости Rb,eff = 9,62 кбит/сек за счетвозрастания вероятности необнаружимой ошибки.Рассмотренные примеры показывают, что выбор кода для каждой конкретной системы должен осуществляться с особой тщательностью.2.4-5.
Расширенные коды ХэммингаВ этом разделе мы рассмотрим весьма полезное расширение кодовХэмминга. Оно заключается в дополнении кодовых векторов дополнительным двоичным разрядом таким образом, чтобы число единиц,содержащихся в каждом кодовом слове, было четно. Коды Хэммингас проверкой на четность обладают следующими двумя преимуществами.• Длины кодов увеличиваются с 2" — 1 до 2П, что удобно с точкизрения хранения и передачи информации.• Минимальное расстояние d m i n расширенных кодов Хэмминга равно 4 вместо 3, что дает возможность обнаруживать 3кратные ошибки.Дополнительный разряд проверки на четность позволяет использовать декодер в новом режиме - гибридном режиме обнаружения икоррекции ошибок.В качестве примера, рассмотрим расширение (15,11)-кода Хэмминга.
Каждый кодовый вектор v = (щ,Ъ\,...,йщ) расширенного(16,11)-кода Хэмминга получается из кодового вектора v = (г?о, V\,V2,• • • > v\i) (15,11)-кода путем добавления дополнительного разряда проверки на четность, т.е.v = («о, vi, ...,щь)= (v0,v0,vi,...,vu),(2.49)где14vo = Y,Vi-i=0(2.50)2-4' Свойства линейных блоковых кодовПроверочная матрица (16,11)-кода получается из проверочной матрицы (15,11)-кода Хэмминга в два приема:-допишем к матрице (15,11)-кода Хэмминга слева нулевой столбец;-дополним получившуюся матрицу строчкой, полностью состоящей из одних единиц.В результате получим/1 1 1 1 1 1 11 1 1 1 1 1 1-1 1\010001001011011100100110010110110001001110011101V 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1/(2.51)При синдромном декодированииI = v 0 Нт,(2.52)причем, правая компонента равна15(2.53)«О =i=0С учетом (2.49) и (2.50), получаем15(2.54)г=0Из (2.49) и (2.51) следует, что и другие компоненты синдрома s такжеравны нулю.Утверждение, что минимальное кодовое расстояние d m i n кодовХэмминга с проверкой на четность равно 4, следует непосредственноиз определения веса кодовых слов.
В самом деле, так как минимальный вес всех векторов кода Хэмминга, за исключением нулевого,равен 3, то дополнительный разряд проверки на четность увеличивает этот минимальный вес до 4. Расширенный код Хэмминга такжеявляется линейным и его минимальное расстояние dm\a = 4.Прежде чем говорить о декодировании кодов Хэмминга с проверкой на четность, напомним два возможных режима декодированияобычных кодов Хэмминга.1.
Режим обнаружения ошибок.Глава 2. Линейные блоковые кодыЕсли синдром s ф 0, то декодер выдает сигнал ошибки. Так какrfmin кода Хэмминга равно 3, то ошибки кратности < 2 всегдаобнаруживаются.2. Режим коррекции ошибок.Если синдром s ф О, то декодер всегда исправляет один из разрядов кодового слова (так как код Хэмминга является плотноупакованным сферами радиуса t = 1). Таким образом, декодерисправляет все однократные ошибки.Из всего вышесказанного видно, что код Хэмминга или толькообнаруживает вес ошибки кратности не выше 2, или только исправляет все однократные ошибки.Теперь перейдем к кодам Хэмминга с проверкой на четность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
