Вернер М. Основы кодирования (2004) (1151849), страница 20
Текст из файла (страница 20)
Однако, корректирующаяспособность кода позволяет снизить результирующую вероятностьнеобнаружимой ошибки (в нашем случае с 1 —0,98 = 0,02 до 7,9-10~5на блок из четырех символов).В настоящее время существует несколько критериев для оценкиэффективности кодирования. В спутниковой связи, например, чащевсего пользуются энергетическим критерием. Сущность его в следующем: так как спутниковые линии связи близки к каналам с АБГШ,вначале находится 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, следует непосредственноиз определения веса кодовых слов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
