Ինքնավերականգնվող կոդեր

Ներածություն

Սխալներ ուղղող կոդերը օգտագործվում են տվյալներին ավելցուկային տարրեր ավելացնելու համար, որպեսզի տվյալները դառնան կայուն սխալների նկատմամբ։
Սովորաբար դա արվում է կոդավորելով բիթերի հաջորդականությունը ավելի երկար հաջորդականությունների, ավելացնելով սկզբնական հաջորդականությանը կառուցվածքային ավելցուկային տարրեր։ Նույնիսկ եթե մի քանի, բայց ոչ շատ բիթեր աղավաղված են, այս եղանակով կառուցվածքային ավելցուկային տարրերը թույլ են տալիս վերականգնել սկզբնական տվյալները։
Սխալներ ուղղող կոդերը գնալով ավելի ու ավելի մեծ կիրառություն են գտնում (օրինակ՝ հեռահաղորդակցման համակարգերում)։ Ենթադրենք ունենք ռադիոալիքային կապի համակարգ։ Հուսալի կապ հաստատելու համար պետք է բարձրացնել հեռահաղորդիչների հզորությունը։ Հուսալիության նույն մակարդակին կարելի է հասնել ներմուծելով սխալներն ուղղող շղթա։ Արդյունքում կապի համակարգը բարդանում է, բայց գումարային ծախսված հզորությունը փոքրանում է կամ էլ հնարավոր է դառնում կապ հաստատել ավելի մեծ հեռավորությունների վրա։
Եթե DVD համակարգերում չօգտագործվեին ՍՈՒԿ-երը, ապա սկավառակի մակերևույթի ամենաանշան քերծվածքը անհնարին կդարձներ DVD-ների հետագա օգտագործումը։ ՍՈՒԿ-երի տեսությունում առանձին ուղղություն է նրանց կիրառումը հիշողություններում։
Նախ քննարկենք մի վայրից դեպի մյուս վայր ինֆորմացիայի փոխանցման ընդհանուր պրոցեսը։ Դիցուք ունենք թվային ինֆորմացիա, որը պետք է աղբյուրից փոխանցենք Ա կետ՝ զգալի հեռավորության վրա։

Կոդավորման տեսություն

Առաջին հերթին ինֆորմացիան անցնում է աղբյուրի կոդերով, ինչի հետևանքով ավելի կոմպակտ տեսք է ստանում։ Այդ ինֆորմացիան անվանվում է աղբյուրի կոդավորված բառ։ Այնուհետև ինֆորմացիան անցնում է կանալի կոդերով, որը ձևափոխում է աղբյուրի կոդավորած բառի սիմվոլների հաջորդականությունը մեկ այլ սիմվոլների հաջորդականությաբ, որը անվանում են կանալի կոդավորված բառ։ Այն իրենից ներկայացնում է ավելի երկար հաջորդականություն, ավելի մեծ հավելումով։
Մոդուլյատորի միջոցով հաջորդականությունը ձևափոխվում է անալոգային ազդանշանի, որը և փոխանցվում է կանալով։ Քանի որ կանալում առաջանում են տարբեր տեսակի աղմուկներ, ապա կանալի ելքը տարբերվում է մուտքից։ Այդ իսկ պատճառով, դեմոդուլյատորով ազդանշանի անցումից հետո, այն պարունակում է սխալներ։ Դեմոդուլացված սիմվոլնորի հաջորդականությունը կոչվում է ընդունված բառ։ Սխալների պատճառով, ընդունված բառի սիմվոլների հաջորդականությունը կարող է չհամնկնել կանալի կոդավորված բառի հետ։ Կոդային բառի դեկոդերը օգտագործում է կանալի կոդային բառի հավելումը՝ընդունված բառի սխալները ուղդելու համար։ Եթե բոլոր սխալները ուղղված են, ապա արդյունքը համընկնում է աղբյուրի կոդային բառի հետ։ Աղբյուրի դեկոդերը կատարում է աղբյուրի կոդերի հակառակ գործողությունը, որի արդյունքը հասնում է Ա կետ։
Սկզբից սխալները ղեկավարող կոդերը ստեղծվել էին կապի կանալի համար։ Սակայն ներկայումս նրանց կիրառությունը շատ բազմազան է։ Մենք կքննարկենք Հեմինգի կոդերը։ Սակայն մինչ դրան անրադառնալը, նախ մի փոքր հասկանանք ինչ է կոդը և ինչ բնութագրեր այն ունի։
Դիցուք մեզ հետաքրքրող ինֆորմացիան կոդավորել ենք երկուական համակարգում։ Կանալով փոխանցելիս, այս ինֆորմացիան կարող է ենթարկվել պատահական սխալների։ Կոդավորման խնդիրն է մեր օգտակար ինֆորմացիային ավելացնել որոշակի քանակությամբ սիմվոլներ, որպեսզի ընդունիչում այդ սխալները հայտնաբերվեն և ուղղվեն։
M հզորությամբ և n երկարությամբ երկուական կոդը իրենից ներկայացնում է n երկարությամբ M հատ երկուական համակարգում գրվաց բառերի բազմություն։ Հիմանակնում M == 2k, այս կոդը անվանում են երկուական (n, k) կոդ։ Ընդհանուր դեպքում կոդերը որոշում են կամայական վերջավոր այբուբենի վրա՝ [0, 1, 2, …, q - 1]։ Գոյություն ունեն կոդերի 2 հիմնական տիպ՝ բլոկային կոդեր և ծառանման կոդեր։ Մեզ հետաքրքրող կոդերը պատկանում են առաջինին։ Բլոկային կոդը k ինֆորմացիոն սիմվոլների բլոկը ներկայացնում է n սիմվոլանի կոդային բառով։

Բլոկային կոդը բնութագրվում է 3 պարամետրերով՝ n բլոկի երկարությամբ, ինֆորմացիայի k երկարությամբ և մինիմալ d հեռավորությամբ։ Վերջինս հանդիսանում է երկու ամենամոտ կոդային բառերի տարբերության չափը. երկու q – ական (x և y) n երկարությամբ հաջորդականությունների միջև բիթ առ բիթ տարբերությունների թիվը կոչվում է Հեմինգի հեռավորություն և նշանակվում է d(x, y)։
Դիցուք հաղորդուոմ ենք կոդային բառ և կանալում տեղի է ունենում մեկ բիթի սխալ։ Այդ դեպքում ընդունված բառը գտնվում է հաղորդված բառից Հեմինգի 1 հեռավորության վրա։ Եթե մյուս բառեռից ունեցած հեռավորությունը ավելին է քան 1, ապա դեկոդերը կուղղի սխալը։ Ընդհանուր դեպքում, եթե տեղի է ունեցել t սխալ, ապա որպեսզի դեկոդերը կարողանա նրանք ուղղել, ապա անհրաժեշտ է, որ d >== 2t + 1

Հեմինգի կոդեր և դեկոդեր

Գոյություն ունեն կոդավորման տարբեր համակարգեր։ Մեր աշխատանքում կդիտարկենք Հեմինգի կոդը։ Այն ընդունակ է գտնել և վերականգնել մեկ բիթի սխալ։ Ներկայիս ժամանակաշրջանում փոխանցվող ինֆորմացիայի ծավալները հասել են այնպիսի մեծ ծավալների, որ նրանց ապահով տեղափոխման և պահպանման համար անհրաժեշտ են ավելի կատարյալ կոդավորման համակարգեր։ Սակայան, գոյություն ունեն այնպիսի բնագավառներ, որտեղ ինֆորմացիան փոխանցվելիս գրեթե կորուստները անհնարին են։ Այդ համակարգերում կարող է օգտագործվել Հեմինգի կոդավորումը՝ պատահական մեկ սխալից համակարգը պաշտպանելու համար։
Նախ եկեք դիտարկենք կոնկրետ օրինակ, այնուհետև կընդհանրացնենք։ Դիցուք մենք ուզում ենք փոխանցել 0101 ինֆորմացիոն բլոկը այնպես, որ ցանկացած 1 բիթ սխալի դեպքում դեկոդերը ոչ միայն կարողանա գրանցել այն, այլ նաև կարողանա վերականգնել ճշգրիտ ինֆորմացիան։ Դրա համար նախ դիտարկենք հետևյալ աղյուսակը.

Դիրք	Կառավարող բիթեր
1 (A)	2^0==1	 Հսկող բիթ
2 (B)	2^1==2	 Հսկող բիթ
3 2^0+2^1==1+2==3	 Կառավարվում է 1 և 2 հսկող բիթերով
4 (C)	2^2==4	 Հսկող բիթ
5	 2^0+2^2==1+4==5	 Կառավարվում է 1 և 4 հսկող բիթերով
6 2^1+2^2==2+4==6	 Կառավարվում է 2 և 4 հսկող բիթերով
7	 2^0+2^1+2^2==1+2+4==7	Կառավարվում է 1, 2 և 4 հսկող բիթերով
8 (D)	2^3==8	 Հսկող բիթ

Աղյուսակի կառուցման սկզբունքը շատ պարզ է։ 2ի աստիճաններին համապատասխան թվերը հանդես են գալիս որպես հսկող բիթեր, իսկ մնացած բոլոր թվերը արտահայտվում են հսկող բիթերի միջոցով։
Այժմ վերադառնանք մեր օրինակին։ Մեր ունեցած 0101 ինֆորմացիոն բլոկը կնդունի հետևյալ տեսքը՝ AB0C101D ։ Այժմ որոշենք A, B, C, D մեծությունները։ Ըստ աղյուսակի, ունենք՝

A == 0, քանի որ A-ն կառավարում է 3, 5 և 7 բիթերը, իսկ վերջիններիս գումարը՝ 0+1+1 զույգ է։
B == 1, քանի որ B-ն կառավարում է 3, 6 և 7 բիթերը, իսկ վերջիններիս գումարը՝ 0+0+1 կենտ է։
C == 0, քանի որ C-ն կառավարում է 5, 6 և 7 բիթերը, իսկ վերջիններիս գումարը՝ 1+0+1 զույգ է։
Հետևաբար, կոդային բառի համար կունենանք՝0100101
Դիցուք բառի փոխանցման դեպքում տեղի է ունենում մեկ բիթի սխալ, և ընդունիչում այն ստանում է 0100111 տեսքը։ Այժմ տեսնենք, թե ինչպես դեկոդերը կվերականգնի ճիշտ ազդանշանը։ Ընդունված ազդանծանի համար ունենք՝

A == (0+1+1)%2 == 0;
B == (0+1+1)%2 == 0;
C == (1+1+1)%2 == 1;

Ինչպես տեսնում ենք, B և C բիթերը չեն համապատասխանում ընդունված բառի միջի B և C բիթերին։ B (2բիթ) և C (4բիթ) բիթերի դիրքերի գումարը կլինի՝ 2+4==6, որն էլ հենց տալիս է շեղված բիթի դիրքը, և ինվերսելով 6րդ բիթը, մենք կվերականգնենք իրական ազդանշանը՝0100101։
Իսկ ինչ կլինի, եթե վնասվի ոչ թե ինֆորմացիոն, այլ հսկող բիթը։ Փորձը ցույց է տալիս, որ այս տեսությամբ վերականգնվում է նաև հսկող բիթում առաջացած սխալը, սակայն, հսկող բիթերը միևնույն է վերջում անջատվում են կոդային բառից, ինֆորմացիոն բառը վերականգնելու համար, այդ իսկ պատճառով, հսկող բիթերի սխալները հիմնականում չեն վերականգնվում դեկոդերում։
Առաջին հայացքից կարծես թե Հեմինգի կեդերը էֆֆեկտիվ չէ, քանի որ մեր օրինակում 4 ինֆորմացիոն բիթի համար պահանջվում է 3 հսկող բիթ։ Սակայն, քանի որ հսկող բիթերը հանդիսանում են 2-ի աստիճաններ, ապա բիթայնության աճի հետ նրանց քանակը զգալիորեն նվազում է։ Ասվածը ավելի ակնառու տեսնելու համար, գրենք մի փոքրիկ C կոդ, որը մեզ ցույց կտա Հեմինգի կոդի արդյունավետության կախումը բիթայնությունից։ Կոդի աշխատանքի արդյունքը բերված է հետևյալ աղյուսակում.

Կոդի չափը Ինֆորմացիայի չափը Էֆֆեկտիվությունը
1 	0 0%
2 	0	 0%
4 	1	 25%
8 	4	 50%
16	 11	 68, 8%
32	 26	 81, 3%
64 	57	 89, 1%
128 	120	 93, 8%
256 	247	 96, 5%
512 	502	 98%
1024	1013	 98, 9%
2048	2036	 99, 4%

main()
{
int a;
int _pow == 1;
int old_pow == 1;
int N, old_N == 1;
printf ( " BLOCK_SIZE FUEL UP EFFICIENCY\n"\
"-----------------------------------\n");
for (a == 0; a < MAX_POW; a++)
{
N == _pow - old_pow - 1 + old_N;
printf("%8d %8d %8.1f%%\n", _pow, N, (float)N / _pow * 100);
// NEXT
old_pow == _pow; _pow == _pow * 2; old_N == N;
} printf("-----------------------------------\n");
}

Կոնկրետ մեր աշխատանքում մենք կդիտարկենք (16, 11) դեպքը, որի էֆֆեկտիվությունը մոտ 70% է, որը շատ համակարգերում բավարար ցուցանիշ է։
Հեմինգի կոդի Verilog կոդը գեներացնելու համար կարելի է օգտագործել C կոդ, որը որպես մւտքային պարամետր կնդունի ինֆորմացիոն բիթերի քանակը, իսկ որպես ելք կտա Verilog կոդը։ Սակայն, քանի որ մեր կոդը այնքան մեծ չէ, իսկ C կոդը ոչ այնքան պարզ, ապա մենք որոշեցինք կոդը գրել ձեռքով՝ օգտվելով վերը նշված աղյուսակային եղանակից։ Այսպիսով, (16, 11) կոդի համար կունենանք.

Դիրք Կառավարող բիթեր
1 (A)	2^0==1	 Հսկող բիթ
2 (B)	2^1==2	 Հսկող բիթ
3	 2^0+2^1==1+2==3	 Կառավարվում է 1 և 2 հսկող բիթերով
4 (C)	2^2==4 Հսկող բիթ
5	 2^0+2^2==1+4==5	 Կառավարվում է 1 և 4 հսկող բիթերով
6 	2^1+2^2==2+4==6	 Կառավարվում է 2 և 4 հսկող բիթերով
7	 2^0+2^1+2^2==1+2+4==7	Կառավարվում է 1, 2 և 4 հսկող բիթերով
8 (D)	2^3==8	 Հսկող բիթ
9	 2^0+2^3==9	 Կառավարվում է 1 և 8 հսկող բիթերով
10	 2^1+2^3==10	 Կառավարվում է 2 և 8 հսկող բիթերով
11	 2^0+2^1+2^3==11	 Կառավարվում է 1, 2 և 8 հսկող բիթերով
12	 2^2+2^3==12	 Կառավարվում է 4 և 8 հսկող բիթերով
13	 2^0+2^2+2^3==13	 Կառավարվում է 1, 4 և 8 հսկող բիթերով
14	 2^1+2^2+2^3==14	 Կառավարվում է 2, 4 և 8 հսկող բիթերով
15	 2^0+2^1+2^2+2^3==15	Կառավարվում է 1, 2, 4 և 8 հսկող բիթերով

Աղյուսակից երևում է, որ ինֆորմացիոն ազդանշանը, որը ունի a1…a11 տեսքը, կոդավորումից հետո կնդունի ABa1Ca2a3a4Da5a6a7a8a9a10a11 տեսքը։ Սխեմատիկորեն այս սարքը պատկերված է նկարում. Եվ այսպես, գրենք Verilog կոդը Հեմինգի կոդերի համար.

module coder (in, out);
input [10։0] in;
output [15։0] out;

wire [10։0] in;
reg[15։0] out;

always @ (in) begin
	out[0]==in[0]^in[1]^in[3]^in[4]^in[6]^in[8]^in[10];
	out[1]==in[0]^in[2]^in[3]^in[5]^in[6]^in[9]^in[10];
	out[2]==in[0];
	out[3]==in[1]^in[2]^in[3]^in[7]^in[8]^in[9]^in[10];
	out[4]==in[1];
	out[5]==in[2];
	out[6]==in[3];
	out[7]==in[4]^in[5]^in[6]^in[7]^in[8]^in[9]^in[10];
	out[8]==in[4];
	out[9]==in[5];
	out[10]==in[6];
	out[11]==in[7];
	out[12]==in[8];
	out[13]==in[9];
	out[14]==in[10];
	out[15]==0;
end
endmodule	

Նմանապես, դեկոդերի համար կստանանք.

module decoder (in, out);
input in;
output out;

wire [15։0] in;
reg [10։0] out;
reg [3։0] check;
reg [4։0] summ;

always @ (in) begin
	 summ==0;
	 check[0]==in[2]^in[4]^in[6]^in[8]^in[10]^in[12]^in[14];
	 check[1]==in[2]^in[5]^in[6]^in[9]^in[10]^in[13]^in[14];
	 check[2]==in[4]^in[5]^in[6]^in[11]^in[12]^in[13]^in[14];
	 check[3]==in[8]^in[9]^in[10]^in[11]^in[12]^in[13]^in[14];
	 if(check[0]!==in[0])
	 	summ==summ+1;
	 if(check[1]!==in[1])
	 	summ==summ+2;	
	 if(check[2]!==in[3])
	 	summ==summ+4;
	 if(check[3]!==in[7])
	 	summ==summ+8;
	 
	 out[0]==in[2];
	 out[1]==in[4];
	 out[2]==in[5];
	 out[3]==in[6];
	 out[4]==in[8];
	 out[5]==in[9];
	 out[6]==in[10];
	 out[7]==in[11];
	 out[8]==in[12];
	 out[9]==in[13];
	 out[10]==in[14];
	 
	 if (summ!==0) begin
	 	case (summ)
	 	4'd3։ out[0]==~out[0];
	 	4'd5։ out[1]==~out[1];
	 	4'd6։ out[2]==~out[2];
	 	4'd7։ out[3]==~out[3];
	 	4'd9։ out[4]==~out[4];
	 	4'd10։ out[5]==~out[5];
	 	4'd11։ out[6]==~out[6];
	 	4'd12։ out[7]==~out[7];
	 	4'd13։ out[8]==~out[8];
	 	4'd14։ out[9]==~out[9];
	 	4'd15։ out[10]==~out[10];
	 	endcase
	 	end
	 	
end
endmodule

Տեստավորում

Այս երկու մոդուլները սինթեզվում են առանց սխալների։ Սակայն, մինչև նրանց նետլիսթերը գեներացնելը, նախ ստուգենք վերջիններիս։ Դրա համար, կառուցենք թեստային շղթան։ Շղթայի աշխատանքի սկզբունքը հետևյալն է։ Counter սարքը գեներացնւմ է 11 բիթ երկարությամբ ինֆորմացիոն բառերի հաջորդական հաջորդականություն։ Ինֆորմացիոն բառերը՝ անցնելով Հեմինգի կոդերվ, կոդավորվևմ են։ Կոդերի ելքը միանում է երկու տարրի, որոնցից մեկը անմիջապես Հեմինգի դեկոդերն է, իսկ մյուսը հանդիսանում է ռեգիստր, որը ամեն նոր եկած կոդավորված բառի հերթական բիթը ինվերսևմ է, այսինքն, արհեստականորեն առաջացնում է կոդավորված բառի մեջ մեկ բիթի սխալ։ Այնուհետև սխալ պարունակող կոդավորված բառը տրվում է երկրորրդ դեկոդերրին։
Շղթայի նպատակն է.

• Գեներացնելով “in” ազդանշանը, համոզվել կոդերի ճիշտ աշխատանքի մեյ, ստուգելով “line” հանգույցի տվեալները։
• Ընդունելով կոդավորված ինֆորմացիան, որը անցնում է “line” հանգույցով, որպես դեկոդերի մուտք, համոզվել, որ դեկոդերը անթերի է աշխատում։**Օգտագործելով “REG & Adder” տարրը, “line2” հանգույցում ստեղծել մեկ բիթի սխալ՝ “line” հանգույցի նկատմամբ։
• Ընդունելով սխալ պարունակող կոդավորված ինֆորմացիան, որը անցնում է “line2” հանգույցով, որպես երկրորրդ դեկոդերի մուտք, համոզվել, որ դեկոդերը անթերի է աշխատում, այսինքն, բացի նրանից որ վերականգնում է ինֆորմացիոն բառը, նաև ուղղում է սխալը։

Վերը նշված շղթան կարելի է իրականացնել հետևյալ կոդի միջոցով.

module top();
reg [10։0] in;
wire [10։0] out;
wire [10։0] out2;
wire [15։0] line;
reg [15։0] line2;
integer error;
reg clk;
coder mycoder (in, line);
decoder truedecoder (line, out);
decoder falsedecoder (line2, out2);
initial begin
in==0;
error==0;
clk==0;
#1 line2==line;
#300 $finish;
end
always #30 clk==~clk;
always @ (posedge clk) begin
in==in+1;
#1 line2==line;
line2[error]==~line[error];
error==error+1;
end
endmodule

Եզրակացություն

Աշխատանքի նպատակն է եղել Հեմինգի կոդերի և դեկոդերի նախագծումը և իրականացումը։ Աշխատանքում օգտագործվել է բազմաբնույթ տեսական գրականություն՝ հարցի տեսական մասը լիարժեք ուսումնասիրելու համար։ Այնուհետև նախագծվել են ծրագրային մոդուլները՝ սարքերի նկարագրման Verilog լեզվով։ Անցնելով սիմուլացիյա և համոզվելով, որ մոդուլները աշխատում են անթերի, գրվել է տեստավորող ծրագիր, որը գեներացնելով սխալներ փոխանցոխ կանալում, տեստավորել է մոդուլնորը։ Համոզվելով, որ ստացված արդյունքները բավարարում են մեր սպասելիքները, գեներացվել է էլեմենտների մաքարդակի Verilog քաղվածք (netlist) երկու մոդուլների համար, օգտագործելով Սինոփսիսի Design Compiler ծրագիրը։ Ստացված քաղվածքները փոխանցվել են Սինոփսիսի IC Compiler ծրագրային գործիքին, որի միջոցով կատարվել է նախագծի վերջնական տեղաբաշխումը (Place & Route) և ծրագծումը (Routing)։

Գրականություն

1. Могущество кодов исправляющих ошибки или информация, воскресшая из пепла. Автор։ Крис Касперски
2. Bleyhut։ Теория и практика кодов контролируящих ошибки
3. Bob Zeidman "Verilog Designer's Library"
4. Скляр Б. - Цифровая связь. Теоретические основы и практическое применение.2003
5. Schulze H., Luders Ch. - Theory and Applications of OFDM and CDMA Wideband Wireless Communications