Здраствуйте ! Подскажите знающие люди , ЧТО ТАКОЕ КОРРЕКТИРУЮЩИЙ ОШИБКИ КОД НА ПРОСТЫХ ЧИСЛАХ (КПЧ) И ГДЕ ПРО НЕГО МОЖНО ПОЧИТАТЬ ??? Прочитал про код Рида-Соломона (например http://ygam.livejournal.com/236181.html). Там сказано, что кодовые слова Рида-Соломона есть многочлены над полями Галуа, которые, грубо говоря, основываются на ПРОСТЫХ ЧИСЛАХ. подскажите : 1 Код Рида-Соломона есть КПЧ ? 2 Если нет, то знаете ли Вы что такое КПЧ или как он еще может называться? Читал про ПУ на: http://ru.wikipedia.org/wiki/Коррекция_ошибок - Общая инфа http://ru.wikibooks.org/wiki/Помехоустойчивое_кодирование - использ. кодов ПУ в OSI, + общ. инфа по основным методам, кратко http://www.kgtu.runnet.ru/WD/TUTOR/net/net3.html - про коды с точки зрения технологий и сетей, уч материал http://www.msclub.ce.cctpu.edu.ru/bibl/PDS/kurs.htm - изложены мат. основы кодирования http://lib.mexmat.ru/books/5119 - Теория корректирующих кодов, книжка, основательно, много математики http://kunegin.narod.ru/ref3/code/index.htm http://kunegin.narod.ru/ref1/coding/index.htm пара рефератов про коды коректирующие и обнаруживающие ошибки, пойдет для начала ознакомления с ПУ http://www.compression.ru/download/articles/ti/potapov_1999_info_theory_pdf.rar методичка по кодированию источников http://www.compression.ru/download/articles/ti/lidovski_2004_information_theory_pdf.rar Учебное пособие по теории информации ну и тд на http://www.compression.ru/download/ti.html http://www.omsu.ru/file.asp?id=1127 книжка Р.Блейхут Теория и практика кодов, контролирующих ошибки (можно исп. как ученик для ВУЗОВ по курсу "Коды, исправляющие ошибки" ) .. там ничего про КПЧ не попалось, все что я знаю про этот код это то что он 1 простой в реализации (не сложнее хеминга) 2 кол-во проверчных битов у него определяется формулой k=]2.4+0.24*m[ ,где m-колво инф. битов) 3 что возможно он блоковый 4 Что если a1 a2 a3 a4 - инф биты, a5 a6 a7 - проверочные (далее '+' это операция XOR), то проверка осущ так: П1 = a1+a2+a5+a7=0 П2=a2+a3+a6+a7=0 .. 5 Что он использует простые числа
Никогда такого кода не встречал. Многие коды используют конечные поля, но прямого отношения к простым числам они не имеют.
4d5a Так как речь идет явно о каком-то линейном коде, могу предположить Simplex Code (он оптимальный линейный). Кода с названием "корректирующий ошибки код на простых числах" естественно не существует и простые числа сами по себе имеют очень приблизительное отношение к кодированию.
Наконец у меня появилось время чтобы описать решение данной задачи. Возможно кому то это пригодится. Задача заключалась именно в <построении п/у кода основанного на простых числах> (те так ее сформулировали преподы одного из пензенских вузов, а целью был диплом. Из разговоров с ними стало ясно что подразумевается кокой то блочный квазисовершенный код , отдаленно напоминающий модифицированный код Хеминга). Так как ответ на вопрос <Существует ли КПЧ> получил отрицательный, то создал его сам. Теперь он существует После нескольких дней читания теории я придумал вот такой метод кодирования. В данном случае исправляется одна, обнаруживаются не более 2, но ‘производительность’ описанного (4,8) кода можно увеличить. Целью работы является демонстация работы ПУ метода в обучающих целях поэтому оптимизация здесь никакая. Код на простых числах: КПЧ (4,8). (4 бит исходн. инфы -> 8 бит кодирован. инфы) (Далее номера битов считаются слева направо) 0) A- исходное сообщ (a1a2a3a4 напр 1001) B- ЗАкодированное (b1b2b3b4b5b6b7b8) 1) Пусть позиция информационных битов определяется простыми числами , позиция p: 2,3,5,7 а в остальных - проверочные биты(S), Тогда кодированное соощение B=b1 b2 b3 b4 b5 b6 b7 b8 B=s1 a1 a2 s2 a3 s3 a4 s4 2) Определим S как s1 = a1 xor a2 xor a3 s2 = a1 xor a2 xor a4 s3 = a1 xor a3 xor a4 s4 = a2 xor a3 xor a4 Например, для A=1001 a1=1 a2=0 a3=0 a4=1 s1=1 s2 =0 s3 = 0 s4 = 1 Т.е. s1 a1 a2 s2 a3 s3 a4 s4 1 2 3 4 5 6 7 8 B= 1 1 0 0 0 0 1 1 3) Вот и закодировали. Пусть теперь испортился любой один бит (1->0 или 0->1) Например испортим при передаче третий бит 0->1 После приема будет s1 a1 a2 s2 a3 s3 a4 s4 1 2 3 4 5 6 7 8 B*= 1 1 1 0 0 0 1 1 4) Выбираем из принятой кодовой комбинации контрольные суммы S* и информационные символы A* s1*=1 s2* =0 s3*= 0 s4* = 1 т.е. S*=1001 A*=1101 Посчитаем контрольные суммы S** по принятым информационным битам A* s1**=a1* xor a2* xor a3* = 1 xor 1 xor 0 =0 s2**=a1* xor a2* xor a4* = 1 s3**=a1* xor a3* xor a4* = 0 s4**=a2* xor a3* xor a4* = 0 5)Составим строку НЕсоответствия контрольных сумм Es= S1* xor S1**= | 1 1 0 1 | Составим матрицу востановления Ms[4][4] Ms= s1 s2 s3 s4 1 | 1 1 1 0 | 2 | 1 1 0 1 | 3 | 1 0 1 1 | 4 | 0 1 1 1 | Найдем в ней строку (n1) соответствующую Es, n1=2, значит повреждению подвергся второй информационный бит, исправим его: a2**=a2* xor 1 остальные оставим без изменения. a1**=a1* a3**=a3* a4**=a4* исправленное сообщение будет таким A**=1001 т.о. была востановлена исходная инфа. Прим. Если Es получилось таким что ему нет соответствия в Ms, то возможны 3 варианта первый вар.: Es=0000, значит ошибки небыло второй вар.: Es есть какая либо строка из единичной матрицы M1s= 1 | 1 0 0 0 | 2 | 0 1 0 0 | 3 | 0 0 1 0 | 4 | 0 0 0 1 | те ошибка возникла в одном из битов контрольных сумм, (например Es= | 0 1 0 0 | ошибка в s2) значит исправлять нечего, инф. биты получены верно третий вар.: в Es какое либо другое значение (напр. Es= | 0 1 1 0 |), значит произошло более одной ошибки, действия по ситуации либо исправлять не будем A*=0 запрос на повторную передачу, либо A**=A* те надеемся что ошики были в s(тогда получим хоть что то вероятность = 1/2, но в это случае следует учитывть что данные недостоверны) Вот таким образом исправляет одиночную ошибку на 1 кодовое слово мой п/у код основанный на простых числах. ссылку на полноценные исходники могу дать после 20.06.07 сейчас приведу только процедуру кодирования/декодирования полубайта( младшие 4 бита ) в байт Код (Text): function Encode(A_In:byte):byte; type t1=array [1..4] of byte; t2=array [1..8] of byte; const A_POS:t1=(2,3,5,7); S_POS:t1=(1,4,6,8); var a,s:t1; z:byte; i:integer; b:t2; begin a[1]:=(A_In and (1 shl 3)) shr 3; a[2]:=(A_In and (1 shl 2)) shr 2; a[3]:=(A_In and (1 shl 1)) shr 1; a[4]:=(A_In and (1 shl 0)) shr 0; s[1]:=a[1] xor a[2] xor a[3]; s[2]:=a[1] xor a[2] xor a[4]; s[3]:=a[1] xor a[3] xor a[4]; s[4]:=a[2] xor a[3] xor a[4]; for i:=1 to 4 do begin b[A_POS[i]]:=a[i]; b[S_POS[i]]:=s[i]; end; z:=0; for i:=1 to 8 do z:=z or((b[i] and 1) shl (8-i) ); result:=z; end; function Decode(B_In:byte ;var ecInf:byte):byte; type t1=array [1..4] of byte; const A_POS:t1=(2,3,5,7); S_POS:t1=(1,4,6,8); C_S:array[1..12] of byte= (1,2,3, 1,2,4, 1,3,4, 2,3,4); var a,s,esum,b:t1; rs,ra:byte; i,j:integer; begin for i:=1 to 4 do begin a[i]:=( B_In and (1 shl (8-A_POS[i])) ) shr (8-A_POS[i]); s[i]:=( B_In and (1 shl (8-S_POS[i])) ) shr (8-S_POS[i]); end; for i:=0 to 3 do begin rs:=s[i+1]; for j:=1 to 3 do rs:=rs xor a[C_S[3*i+j]]; esum[i+1]:= rs; end; rs:=0; for i:=1 to 4 do rs:=rs or ((esum[i]) shl (4-i)); // // case rs of 0: ecInf:=0{not err}; $07: begin a[4]:= a[4] xor 1; ecInf:=1; end; // rs=1110 $0b: begin a[3]:= a[3] xor 1; ecInf:=1; end; // rs=1101 $0d: begin a[2]:= a[2] xor 1; ecInf:=1; end; // rs=1011 $0e: begin a[1]:= a[1] xor 1; ecInf:=1; end; // rs=0111 $01: ecInf:=0; $02: ecInf:=0; $04: ecInf:=0; $08: ecInf:=0; else ecInf:=10; {more or equ 2 err}; end; ra:=0; for i:=1 to 4 do ra:=ra or (a[i] shl (4-i)); result:=ra; { MxCorrect= array [1..32] of byte ( 1,0,0,0 1,1,0,1 1,0,1,1 0,1,0,0 1,0,1,1 0,0,1,0 0,1,1,1 0,0,0,1 ); for i:=1 to 4 do b[i]:=( B_In and (1 shl (8-i)) ) shr (8-i); b[4+i]:=( B_In and (1 shl (4-i)) ) shr (4-i); while (j<8) and ( not ( (esum[1]=MxCorrect[j*4+1]) and (esum[2]=MxCorrect[j*4+2]) and (esum[3]=MxCorrect[j*4+3]) and (esum[4]=MxCorrect[j*4+4]) )) do Inc(j); if (j<8) then b[i]:= b[i] xor 1; } end;
4d5a Да нет, не напоминающий.. Это он и есть. Расширенный Hamming code Hamming(8,4) (в другой записи HAM(3,2)) с битом паритета, также известный под названием Bauer code. Если нужно наглядное построение, то лучше всего через многомерную (в данном случае трехмерную) решетку. Простые числа здесь - не пришей кобыле хвост.. В общем велосипед изобретен успешно Только не стоит его в таком виде где-нибудь кроме диплома использовать - засмеют.
Тоже сложилось впечатление, что это одно и то же. Просто разница в размещении информационных разрядов, в которой выигрыша/проигрыша мне (пока) не видно. Где же здесь простые числа и их свойства используются?
Вот как работает RAID-массив на остатках от деления на простое число =))). Излагаю вариант, когда места потерянных символов известны. Простое число пусть будет, эээ… 257. Пусть 5 устройств будут пользовательскими, а 3 - проверочными. Матрица Вандермонда A(i,j)=i^(j-1): 1 1 1 1 1 1 2 4 8 16 1 3 9 27 81 Наши данные, например, D= 7 15 144 200 250 Вычисляем проверочные данные R=A*D mod 257: R= 102 45 13 Теперь, положим, мы потеряли тома сo значением 15, 200, 250 Берем вместо пользовательских томов три резервных тома: X= 7 102 144 45 13 Матрица для лечения будет B= 1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 2 4 8 16 1 3 9 27 81 Тут самое интересное! Эту матрицу нужно О-Б-Е-Р-Н-У-Т-Ь!!! Обратной матрицей будет: I= 1 0 0 0 0 135 25 163 58 39 0 0 1 0 0 51 151 163 59 253 70 82 187 140 222 Умножаем теперь I*X mod 257 и получаем 7 15 144 200 250 Урра!!!! Три случайных диска грохнули и все пять восстановили!!! А вот этим кодом мы оборачивали матрицу =))). Код (Text): for k=1:5, p=a(k,k); a(k,k)=1; for i=1:5, if i != k, a(k,i)=-a(k,i); end; end; for i=1:5, for j=1:5, if (i !=k ) && (j != k), a(i,j)=a(i,j)*p+a(i,k)*a(k,j); end; end; end; for i=1:256, if mod(i*p,257) == 1, inv_el=i; end; end; for i=1:5, for j=1:5, a(i,j)=mod(a(i,j)*inv_el,257); end; end; end;
