(Self Repair Mechanism, Codes, Recovery, self-correcting, Teorie kodovani)
Paritni bit (Parity bit) Kontrola, zda je pocet stejnych bitu sudy nebo lichy. 111010010011 -- 11 (not inp = 000101101100) <0-1> a) funkce SUMA a + b + c ... = 1+1+1+0+1+0+0+1+0+0+1+1 = 7 and 1 = 1 (lichy pocet jednicek v inp) a + b + c ... = 0+0+0+1+0+1+1+0+1+1+0+0 = 5 and 1 = 1 (lichy pocet nul v inp) b) funkce XOR a xor b xor c ... (111010010011) = 1 (lichy pocet jednicek v inp) a xor b xor c ... (000101101100 = not inp) = 1 (lichy pocet nul v inp) Parita byte (Parity byte) 211 22 3 45 0 67 92 -- 184 <0-255> Suma = 211+22+3+45+0+67+92 = 440 and 255 = 184 Soucet bytu (Suma bytes) 211 22 3 45 0 67 92 -- 184 <0-255> Suma = 211+22+3+45+0+67+92 = 440 XOR bytu 211 22 3 45 0 67 92 -- 244 <0-255> 11010011 00010110 00000011 00101101 00000000 01000011 01011100 -------- 11110100 = 244 (Kdyz je pocet jednicek ve sloupci lichy, vysledek je 1) Nevyhodou je, ze staci 2 chyby na te same pozici se vyrusi, xor je neukaze. Soucty souctu, parit 111010010011 -- 0 ...1...0...1 parita(parita(4-bit block)) = 0 211 22 3 45 0 67 92 0 -- 184 233 48 67 92 = suma(suma 2 byte block) = 184 MD2-MD6, SHA0-SHA3 (Keccak) hash (MD Message Digest, SHA Secure Hash Algorithm) Jsou to slozitejsi blokove kontrolni soucty. MD5 (cast algoritmu) 0 ≤ i ≤ 15: F = (B and C) or ((not B) and D) 16 ≤ i ≤ 31: F = (D and B) or ((not D) and C) 32 ≤ i ≤ 47: F = B xor C xor D 48 ≤ i ≤ 63: F = C xor (B or (not D)) SHA1 (cast algoritmu) 0 ≤ i ≤ 19: f = (b and c) or ((not b) and d) 20 ≤ i ≤ 39: f = b xor c xor d 40 ≤ i ≤ 59: f = (b and c) or (b and d) or (c and d) 60 ≤ i ≤ 79: f = b xor c xor d CRC hash (Cyclic redundancy check) Udajne se da CRC pouzit i k oprave chyb. Matematicky: Sčítání polynomů v konečném tělese GF(2^n) A = 100101 = 1*x^5 + 1*x^2 + 1*x^0 = x^5 + x^2 + 1 B = 110011 = x^5 + x^4 + x + 1 A xor B = 010110 = x^4 + x^2 + x = C A + B = (x^5 + x^2 + 1) + (x^5 + x^4 + x + 1) = 2x^5 + x^4 + x^2 + x + 2 = vse dvojnasobne se vyrusi = x^4 + x^2 + x = C Delitel (polynom) je zvolene cislo. Pro 16-bit je dobry 8D95, 1000110110010101. Melo by asi obsahovat co nejvic stridani 0 a 1. Navic, muzeme vygenerovat tabulku a pri kazde rotaci pouzit jiny polynom. Pred Input dame jednicku. Za input nulove bity podle delky delitele (o jeden mene, 4-1=3). A pak postupne xorujeme a rotujeme delitel, dokud neni prvni cast nulova (bez poslednich 3 bitu). Ty jsou pak CRC hash. Cim vetsi je delitel, tim je vetsi pravdepodobnost, ze jsou data neporusena, ale neni to 100%. 11010011101100 000 <--- input (14 bit) + 3 nulove bity (3 = 4 (delitel) - 1) 1011 <--- delitel (4 bity) = 1101 = polynom x^3 + x + 1 (4 bit = CRC-3) 01100011101100 000 <--- vysledek 1011 <--- delitel, posun/rotace doprava 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- delitel, posun se az k jednicce 1011 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ------------------ 00000000000000 100 <--- prvni cast je 0, konec, posledni 3 bity jsou CRC hash. crc_remainder('11010011101100', '1011', '0') = '100' crc_check( '11010011101100', '1011', '100') = True Blake3, Blake2 (in rar5) https://en.wikipedia.org/wiki/BLAKE_(hash_function) BLAKE j = sigma_table[r%10][2*i] // Index computations (i = data index = 0..n) k = sigma_table[r%10][2*i+1] a = a + b + (message[j] xor n_const[k]) // Step 1 (with input) d = (d xor a) >>> 16 c = c + d // Step 2 (no input) b = (b xor c) >>> 12 a = a + b + (message[k] xor n_const[j]) // Step 3 (with input) d = (d xor a) >>> 8 c = c + d // Step 4 (no input) b = (b xor c) >>> 7 Fletcher4 (1970, in ZFS) Slabina: Kdyz jsou data binarne 00000000 nebo 11111111, tak je povazuje za stejne. Fletcher A = 0, B = 0 A += Data[i] B += A base8 = value mod 256 Output = base8(A), base8(B) Fletcher example i Data A B - - 0 0 1 163 163 163 2 200 363 526 3 19 382 908 4 74 456 1364 5 88 544 1908 Output = base8(544), base8(1908) = 34, 123 Fletcher4 A = 0, B = 0, C = 0, D = 0 A += Data[i] B += A C += B D += C base8 = value mod 256 Output = base8(A), base8(B), base8(C), base8(D) Fletcher ASM .sloop vpmovzxdq data, [buf] ; loads DWORD data into QWORD lanes add buf, 16 vpaddq a, a, data vpaddq b, b, a vpaddq c, c, b vpaddq d, d, c cmp buf, end jb .sloop Adler-32 CheckSum (1995, in zlib) D = Wikipedia = 87 105 107 105 112 101 100 105 97 MOD_ADLER = 65521 // for 16-bit checksum A0 = 1 B0 = 0 A1 = 1 + D1 = 1 + 87 = 88 // An = ( A(n-1) + D(n) ) % MOD_ADLER; ('W') B1 = 0 + A1 = 0 + 88 = 88 // Bn = ( suma(B(n-1)) + A(n) ) % MOD_ADLER; A2 = 88 + 105 = 193 ('i') B2 = 88 + 193 = 281 A2 = 193 + 107 = 300 ('k') B2 = 281 + 300 = 581 ... An = 823 + 97 = 920 ('a') Bn = 3662 + 920 = 4582 base16 = value mod 65536 Output = base16(4582), base16(920) = 0x11E6, 0x398 Zedmee https://github.com/matteo65/ZedmeeHash h = table[(--length + data[pos + length]) & 0xFF] xor ((h << 2) + h); Dalsi funkce Arash Partow Bernstein FNV-1a Hanson iSCSI CRC K&R Larson lookup3 MaPrime2c Meiyan Murmur2 Murmur2A Murmur3 Novak unrolled One At Time Paul Hsieh Ramakrishna RIPEMD SBox Sedgewick SHAKE128 TIGER Weinberger Whirlpool (AES) x17 unrolled x65599 XXHfast32 XXHstrong32 https://www.strchr.com/hash_functionsTop
RAID Parity (XOR) funkce XOR abc|d d = a xor b xor c 000|0 c = d xor a xor b 001|1 b = c xor d xor a 010|1 a = b xor c xor d 011|0 100|1 101|0 110|0 111|1 Mame 3 casti disku A, B, C. K nim vytvorime 4tou cast D pomoci funkce XOR. 101101 A -- disk 1 (data) 001011 B -- disk 2 (data) 100100 C -- disk 3 (data) -------- 000010 D = A XOR B XOR C -- disk 4 (opravny disk, recovery data) Pokud pomoci CheckSum zjistime, ze je nejaky disk vadny, tak jej lze cely dopocitat pomoci recodery disku pomoci funkce XOR. Obnova disku B pomoci A, C a D 101101 A 100100 C 000010 D -------- 001011 B = A XOR D XOR C Muzete disk rozdelit na 6 casti a ulozit si xor pro 3 a 3 casti a pak pro nahodne 4 ze vsech 6. Hammingův kód (1950, flash disk USB) Pozn.: Sorry, strasne slozity mat. vyklad. https://cs.wikipedia.org/wiki/Hamming%C5%AFv_k%C3%B3d#Hamming%C5%AFv_k%C3%B3d_(7,4) Pro 4 bity abcd P xor a xor b xor c = 0 Q xor a xor b xor d = 0 R xor d xor b xor c = 0 JS kod pro kodovani
function hammingEncode(input) {
if (typeof input !== 'string' || input.match(/[^10]/)) {
return console.error('hamming-code error: input should be binary string,
for example "101010"');
}
var output = input;
var controlBitsIndexes = [];
var controlBits = [];
var l = input.length;
var i = 1;
var key, j, arr, temp, check;
while (l / i >= 1) {
controlBitsIndexes.push(i);
i *= 2;
}
for (j = 0; j < controlBitsIndexes.length; j++) {
key = controlBitsIndexes[j];
arr = output.slice(key - 1).split('');
temp = chunk(arr, key);
check = (temp.reduce(function (prev, next, index) {
if (!(index % 2)) {
prev = prev.concat(next);
}
return prev;
}, []).reduce(function (prev, next) { return +prev + +next },
0) % 2) ? 1 : 0;
output = output.slice(0, key - 1) + check + output.slice(key - 1);
if (j + 1 === controlBitsIndexes.length && output.length / (key * 2) >= 1) {
controlBitsIndexes.push(key * 2);
}
}
return output;
}
Reedovy–Solomonovy kódy (CD disky) Pozn.: Sorry, strasne slozity mat. vyklad s furierovou transformaci. https://cs.wikipedia.org/wiki/Reedovy%E2%80%93Solomonovy_k%C3%B3dy - odkazuji na BCH https://cs.wikipedia.org/wiki/BCH_k%C3%B3d Opakovací kód Bity se vysilaji 3x, 2 ze 3 shodnych se povazuji za spravne. 000 0 (00x) 001 0 (00x) 010 0 (00x) 011 1 (11x) 100 0 (00x) 101 1 (11x) 110 1 (11x) 111 1 (11x) Protoze chyby vetsinou poskodi nekolik bitu po sobe je vyhodnejsi rozdelit zpravu na bloky a ty zopakovat 3x za sebou. Oprava sumem Mame 2 prenasene kanaly. Jednim posilame data, druhy ma predem urceny signal. Pokud vznikne sum (radiove ruseni) na dratu, predpoklada se, ze narusi oba kanaly stejne. Z druheho kanalu muzeme vyrobit sum, ktery odecteme od prvniho kanalu a ziskame mozn neposkozena data. Seznam samoopravných kódů AN kódy BCH kód, který lze navrhnout tak, aby opravoval libovolný počet chyb v kódovém bloku Barkerův kód používán pro radary, telemetrii, ultrazvuk, Wifi, sítě mobilní telefonů DSSS, GPS Bergerův kód Kód s konstantní váhou Konvoluční kód Expanderové kódy Skupinové kódy Golayovy kódy, z nichž Binární Golayův kód má praktický význam Goppův kód používaný v McEliecově kryptosystému Hadamardův kód Hagelbargerův kód Hammingův kód Kód vycházející z latinského čtverce pro nebílý šum (převládající například při vysokorychlostních přenosech po napájecích vodičích) Lexikografický kód Lineární síťové kódování typ výmazového opravného kódu přes síť místo dvoubodové spoje Dlouhý kód Nízkohustotní kód s kontrolou parity, také známý jako Gallagerův kód, jako archetyp řídkých grafových kódů LT kód je téměř optimální Fountainův kód Kód m z n Nordstromův-Robinsonův kód, používaný v geometrii a teorii grup[24] Online kód, téměř optimální Fountainův kód Polární kód (teorie kódování) Raptor kód, téměř optimální Fountainův kód Reedovy–Solomonovy kódy Reedův–Mullerův kód Opakovat-accumulate kód Opakovací kódy, např. trojnásobná modulární redundance Spinální kód, bezpoměrový, nelineární kód založený na pseudonáhodných hashovacích funkcích Tornado kód, téměř optimální výmazový kód, předchůdce Fountainových kódů Turbokód Walshův–Hadamardův kód Cyklický redundantní součet (CRCs) Viterbiho algoritmus Dopředná oprava chyb (FEC) LDPC (parita)Top
abcd|e e = a xor b xor c xor d 0000|0 0001|1 abc|d d = a xor b xor c 0010|1 000|0 c = d xor a xor b 0011|0 001|1 b = c xor d xor a 0100|1 010|1 a = b xor c xor d 0101|0 011|0 0110|0 100|1 0111|1 101|0 1000|1 110|0 1001|0 111|1 1010|0 1011|1 ab|c c = a xor b 1100|0 00|0 b = c xor a 1101|1 01|1 a = b xor c 1110|1 10|1 1111|0 11|0 Xor ma na vystupu jednicku, kdyz je pocet jednicek vstupu lichy. https://web.stanford.edu/class/cs103/tools/truth-table-tool/ Zajimave vlastnosti a xor b = b xor a (a xor b) xor c = a xor (b xor c) a xor b xor b = a b xor a xor a = b a xor a = 0 a xor 0 = aTop