êóðñîâûå,êîíòðîëüíûå,äèïëîìû,ðåôåðàòû
Ïðåïîäàâàòåëü: Ñìåðäîâà Í. Å.
Ãðóïïà: ÐÒ 9505
Ñòóäåíò: Ìàòâååâ À. Í.
Äàòà ñäà÷è: Ìàé 1999 ãîäà.
Ìîñêâà, 1999 ã.
Âñòóïëåíèå.
Èçâåñòíî, ÷òî êàíàëû, ïî êîòîðûì ïåðåäàåòñÿ èíôîðìàöèÿ, ïðàêòè÷åñêè íèêîãäà íå áûâàþò èäåàëüíûìè (êàíàëàìè áåç ïîìåõ).  íèõ ïî÷òè âñåãäà ïðèñóòñòâóþò ïîìåõè. Îòëè÷èå ëèøü â óðîâíå ïîìåõ è èõ ñïåêòðàëüíîì ñîñòàâå. Ïîìåõè â êàíàëàõ îáðàçóþòñÿ ïî ðàçëè÷íûì ïðè÷èíàì, íî ðåçóëüòàò âîçäåéñòâèÿ èõ íà ïåðåäàâàåìóþ èíôîðìàöèþ âñåãäà îäèí – èíôîðìàöèÿ òåðÿåòñÿ (èñêàæàåòñÿ).
Äëÿ ïðåäîòâðàùåíèÿ ïîòåðü èíôîðìàöèè â êàíàëå áûëè ïðèäóìàíû èçáûòî÷íûå êîäû (êîäû ñ èçáûòî÷íîñòüþ). Ïðåèìóùåñòâî èçáûòî÷íîãî êîäà â òîì, ÷òî ïðè ïðèåìå åãî ñ èñêàæåíèåì (êîëè÷åñòâî èñêàæåííûõ ñèìâîëîâ çàâèñèò îò ñòåïåíè èçáûòî÷íîñòè è ñòðóêòóðû êîäà) èíôîðìàöèÿ ìîæåò áûòü âîññòàíîâëåíà íà ïðèåìíèêå.
Ñóùåñòâóþò èçáûòî÷íûå êîäû ñ îáíàðóæåíèåì (îíè òîëüêî îáíàðóæèâàþò îøèáêó) è êîäû ñ èñïðàâëåíèåì (ýòè êîäû îáíàðóæèâàþò ìåñòî îøèáêè è èñïðàâëÿþò åå).
Äëÿ ðàçëè÷íûõ ïîìåõ â êàíàëå ñóùåñòâóþò ðàçëè÷íûå ïî ñâîåé ñòðóêòóðå è èçáûòî÷íîñòè êîäû. Îáû÷íî èçáûòî÷íîñòü êîäîâ íàõîäèòñÿ â ïðåäåëàõ 10…60% èëè ÷óòü áîëüøå. Èçáûòî÷íîñòü 1/4 (25%) ïðèìåíÿåòñÿ ïðè çàïèñè èíôîðìàöèè íà ëàçåðíûå äèñêè è â ñèñòåìàõ öèôðîâîãî ñïóòíèêîâîãî ÒÂ.
Êëàññèôèêàöèÿ êîäîâ.
Èçâåñòíî áîëüøîå ÷èñëî ïîìåõîóñòîé÷èâûõ êîäîâ, êîòîðûå êëàññèôèöèðóþòñÿ ïî ðàçëè÷íûì ïðèçíàêàì. Ïîìåõîóñòîé÷èâûå êîäû ìîæíî ðàçäåëèòü íà äâà áîëüøèõ êëàññà: áëî÷íûå è íåïðåðûâíûå. Ïðè áëî÷íîì êîäèðîâàíèè ïîñëåäîâàòåëüíîñòü ýëåìåíòàðíûõ ñîîáùåíèé èñòî÷íèêà ðàçáèâàåòñÿ íà îòðåçêè è êàæäîìó îòðåçêó ñòàâèòñÿ â ñîîòâåòñòâèå îïðåäåëåííàÿ ïîñëåäîâàòåëüíîñòü (áëîê) êîäîâûõ ñèìâîëîâ, íàçûâàåìàÿ îáû÷íî êîäîâîé êîìáèíàöèåé. Ìíîæåñòâî âñåõ êîäîâûõ êîìáèíàöèé, âîçìîæíûõ ïðè äàííîì ñïîñîáå áëî÷íîãî êîäèðîâàíèÿ, è åñòü áëî÷íûé êîä.
Äëèíà áëîêà ìîæåò áûòü êàê ïîñòîÿííîé, òàê è ïåðåìåííîé. Ðàçëè÷àþò ðàâíîìåðíûå è íåðàâíîìåðíûå áëî÷íûå êîäû. Ïîìåõîóñòîé÷èâûå êîäû ÿâëÿþòñÿ, êàê ïðàâèëî, ðàâíîìåðíûìè.
Áëî÷íûå êîäû áûâàþò ðàçäåëèìûìè è íåðàçäåëèìûìè. Ê ðàçäåëèìûì îòíîñÿòñÿ êîäû, â êîòîðûõ ñèìâîëû ïî èõ íàçíà÷åíèþ ìîãóò áûòü ðàçäåëåíû íà èíôîðìàöèîííûå ñèìâîëû, íåñóùèå èíôîðìàöèþ î ñîîáùåíèÿõ è ïðîâåðî÷íûå. Òàêèå êîäû îáîçíà÷àþòñÿ êàê (n, k), ãäå n- äëèíà êîäà, k- ÷èñëî èíôîðìàöèîííûõ ñèìâîëîâ. ×èñëî êîìáèíàöèé â êîäå íå ïðåâûøàåò 2^k. Ê íåðàçäåëèìûì îòíîñÿòñÿ êîäû, ñèìâîëû êîòîðûõ íåëüçÿ ðàçäåëèòü ïî èõ íàçíà÷åíèþ íà èíôîðìàöèîííûå è ïðîâåðî÷íûå.
Êîäû ñ ïîñòîÿííûì âåñîì õàðàêòåðèçóþòñÿ òåì, ÷òî èõ êîäîâûå êîìáèíàöèè ñîäåðæàò îäèíàêîâîå ÷èñëî åäèíèö: Ïðèìåðîì òàêîãî êîäà ÿâëÿåòñÿ êîä “3 èç 7”, â êîòîðîì êàæäàÿ êîäîâàÿ êîìáèíàöèÿ ñîäåðæèò òðè åäèíèöû è ÷åòûðå íóëÿ (ñòàíäàðòíûõ òåëåãðàôíûé êîä ¹ 3).
ãäå Pîø âåðîÿòíîñòü èñêàæåíèÿ ñèìâîëà.
Ñðåäè ðàçäåëèìûõ êîäîâ ðàçëè÷àþò ëèíåéíûå è íåëèíåéíûå. Ê ëèíåéíûì îòíîñÿòñÿ êîäû, â êîòîðûõ ïîðàçðÿäíàÿ ñóììà ïî ìîäóëþ 2 ëþáûõ äâóõ êîäîâûõ ñëîâ òàêæå ÿâëÿåòñÿ êîäîâûì ñëîâîì. Ëèíåéíûé êîä íàçûâàåòñÿ ñèñòåìàòè÷åñêèì, åñëè ïåðâûå k ñèìâîëîâ åãî ëþáîé êîäîâîé êîìáèíàöèè ÿâëÿþòñÿ èíôîðìàöèîííûìè, îñòàëüíûå (n- k) ñèìâîëîâ — ïðîâåðî÷íûìè.
Ïîäêëàññîì ëèíåéíûõ êîäîâ ÿâëÿþòñÿ öèêëè÷åñêèå êîäû. Îíè õàðàêòåðèçóþòñÿ òåì, ÷òî âñå íàáîðû, îáðàçîâàííûå öèêëè÷åñêîé ïåðåñòàíîâêîé ëþáîé êîäîâîé êîìáèíàöèè, ÿâëÿþòñÿ òàêæå êîäîâûìè êîìáèíàöèÿìè. Ýòî ñâîéñòâî ïîçâîëÿåò â çíà÷èòåëüíîé ñòåïåíè óïðîñòèòü êîäèðóþùåå è äåêîäèðóþùåå óñòðîéñòâà, îñîáåííî ïðè îáíàðóæåíèè îøèáîê è èñïðàâëåíèè îäèíî÷íîé îøèáêè. Ïðèìåðàìè öèêëè÷åñêèõ êîäîâ ÿâëÿþòñÿ êîäû Õýììèíãà, êîäû Áîóçà - ×îóäõóðè - Õîêâèíãåìà (Á×Õ — êîäû) è äð.
Ïðèìåðîì íåëèíåéíîãî êîäà ÿâëÿåòñÿ êîä Áåðãåðà, ó êîòîðîãî ïðîâåðî÷íûå ñèìâîëû ïðåäñòàâëÿþò äâîè÷íóþ çàïèñü ÷èñëà åäèíèö â ïîñëåäîâàòåëüíîñòè èíôîðìàöèîííûõ ñèìâîëîâ. Íàïðèìåð, òàêèì ÿâëÿåòñÿ êîä: 00000; 00101; 01001; O111O; 10001; 10110; 11010; 11111. Êîäû Áåðãåðà ïðèìåíÿþòñÿ â àñèììåòðè÷íûõ êàíàëàõ.  ñèììåòðè÷íûõ êàíàëàõ îíè îáíàðóæèâàþò âñå îäèíî÷íûå îøèáêè è íåêîòîðóþ ÷àñòü ìíîãîêðàòíûõ.
Íåïðåðûâíûå êîäû õàðàêòåðèçóþòñÿ òåì, ÷òî îïåðàöèè êîäèðîâàíèÿ è äåêîäèðîâàíèÿ ïðîèçâîäÿòñÿ íàä íåïðåðûâíîé ïîñëåäîâàòåëüíîñòüþ ñèìâîëîâ áåç ðàçáèåíèÿ åå íà áëîêè. Ñðåäè íåïðåðûâíûõ íàèáîëåå ïðèìåíèìû ñâåðòî÷íûå êîäû.
Êàê èçâåñòíî ðàçëè÷àþò êàíàëû ñ íåçàâèñèìûìè è ãðóïïèðóþùèìèñÿ îøèáêàìè. Ñîîòâåòñòâåííî ïîìåõîóñòîé÷èâûå êîäû ìîæíî ðàçáèòü íà äâà êëàññà: èñïðàâëÿþùèå íåçàâèñèìûå îøèáêè è èñïðàâëÿþùèå ïàêåòû îøèáîê. Äàëåå áóäóò ðàññìàòðèâàòüñÿ â îñíîâíîì êîäû, èñïðàâëÿþùèå íåçàâèñèìûå îøèáêè. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî õîòÿ äëÿ èñïðàâëåíèÿ ïàêåòîâ îøèáîê ðàçðàáîòàíî ìíîãî ýôôåêòèâíûõ êîäîâ, íà ïðàêòèêå öåëåñîîáðàçíåå èñïîëüçîâàòü êîäû, èñïðàâëÿþùèå íåçàâèñèìûå îøèáêè âìåñòå ñ óñòðîéñòâîì ïåðåìåæåíèÿ ñèìâîëîâ èëè äåêîððåëÿöèè îøèáîê. Ïðè ýòîì ñèìâîëû êîäîâîé êîìáèíàöèè íå ïåðåäàþòñÿ äðóã çà äðóãîì, ïåðåìåøèâàþòñÿ ñ ñèìâîëàìè äðóãèõ êîäîâûõ êîìáèíàöèé. Åñëè èíòåðâàë ìåæäó ñèìâîëàìè, ïðèíàäëåæàùèìè îäíîé êîäîâîé êîìáèíàöèè, ñäåëàòü áîëüøå ÷åì “ïàìÿòü” êàíàëà, òî îøèáêè â ïðåäåëàõ êîäîâîé êîìáèíàöèè ìîæíî ñ÷èòàòü íåçàâèñèìûìè, ÷òî è ïîçâîëÿåò èñïîëüçîâàòü êîäû, èñïðàâëÿþùèå íåçàâèñèìûå îøèáêè.
Áëî÷íûå êîäû. Ïîñòðîåíèå êîäåêîâ.
Ëèíåéíûå êîäû.
Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ëþáîé ëèíåéíûé êîä (ï, k) ìîæíî ïîëó÷èòü èç k ëèíåéíî íåçàâèñèìûõ êîäîâûõ êîìáèíàöèé ïóòåì èõ ïîñèìâîëüíîãî ñóììèðîâàíèÿ ïî ìîäóëþ 2 â ðàçëè÷íûõ ñî÷åòàíèÿõ. Èñõîäíûå ëèíåéíî íåçàâèñèìûå êîäîâûå êîìáèíàöèè íàçûâàþòñÿ áàçèñíûìè.
Ïðåäñòàâèì áàçèñíûå êîäîâûå êîìáèíàöèè â âèäå ìàòðèöû ðàçìåðíîñòüþ nXk
(7.7)
 òåîðèè êîäèðîâàíèÿ îíà íàçûâàåòñÿ ïîðîæäàþùåé. Òîãäà ïðîöåññ êîäèðîâàíèÿ çàêëþ÷àåòñÿ â âûïîëíåíèè îïåðàöèè: B=AG,
ãäå À- âåêòîð ðàçìåðíîñòüþ k, ñîîòâåòñòâóþùèé ñîîáùåíèþ, Â- âåêòîð ðàçìåðíîñòüþ ï, ñîîòâåòñòâóþùèé êîäîâîé êîìáèíàöèè.
äâîè÷íûõ ñèìâîëîâ.
Äâå ïîðîæäàþùèå ìàòðèöû, êîòîðûå îòëè÷àþòñÿ äðóã îò äðóãà òîëüêî ïîðÿäêîì ðàñïîëîæåíèÿ ñòîëáöîâ, çàäàþò êîäû, êîòîðûå èìåþò îäèíàêîâûå ðàññòîÿíèÿ Õýììèíãà ìåæäó ñîîòâåòñòâóþùèìè êîäîâûìè êîìáèíàöèÿìè, à ñëåäîâàòåëüíî, îäèíàêîâûå êîððåêòèðóþùèå ñïîñîáíîñòè. Òàêèå êîäû íàçûâàþòñÿ ýêâèâàëåíòíûìè.
ãäå I- åäèíè÷íàÿ kXk ïîäìàòðèöà, P-kX(n-k)- ïîäìàòðèöà ïðîâåðî÷íûõ ñèìâîëîâ, îïðåäåëÿþùàÿ ñâîéñòâà êîäà. Ìàòðèöà çàäàåò ñèñòåìàòè÷åñêèé êîä. Ìîæíî ïîêàçàòü, ÷òî äëÿ ëþáîãî ëèíåéíîãî êîäà ñóùåñòâóåò ýêâèâàëåíòíûé ñèñòåìàòè÷åñêèé êîä.
ãäå P - ïîäìàòðèöà, ñòîëáöàìè êîòîðîé ñëóæàò ñòðîêè ïîäìàòðèöû Ð (7.8), I-åäèíè÷íàÿ rXr ïîäìàòðèöà. Ïîäñòàâëÿÿ (7.10) â (7.9), ìîæíî ïîëó÷àòü ï—k óðàâíåíèé âèäà (7.11)
Î÷åâèäíî, ÷òî ëèíåéíûé (ï, k) êîä ìîæíî ïîñòðîèòü, èñïîëüçóÿ óðàâíåíèÿ ïðîâåðêè (7.11). Ïðè ýòîì ïåðâûå k ñèìâîëîâ êîäîâîé êîìáèíàöèè èíôîðìàöèîííûå, à îñòàëüíûå ï-k ñèìâîëîâ - ïðîâåðî÷íûå, îáðàçóåìûå â ñîîòâåòñòâèè ñ (7.11).
Ñ ïîìîùüþ ïðîâåðî÷íîé ìàòðèöû ñðàâíèòåëüíî ëåãêî ìîæíî ïîñòðîèòü êîä ñ çàäàííûì êîäîâûì ðàññòîÿíèåì. Ýòî ïîñòðîåíèå îñíîâàíî íà ñëåäóþùåé òåîðåìå: êîäîâîå ðàññòîÿíèå ëèíåéíîãî (ï, k) êîäà ðàâíî d òîãäà è òîëüêî òîãäà, êîãäà ëþáûå d-1 ñòîëáöîâ ïðîâåðî÷íîé ìàòðèöû ýòîãî êîäà ëèíåéíî íåçàâèñèìû, íî íåêîòîðûå d ñòîëáöîâ ïðîâåðî÷íîé ìàòðèöû ëèíåéíî çàâèñèìû.
Çàìåòèì, ÷òî ñòðîêè ïðîâåðî÷íîé ìàòðèöû ëèíåéíî íåçàâèñèìûå. Ïîýòîìó ïðîâåðî÷íóþ ìàòðèöó ìîæíî èñïîëüçîâàòü â êà÷åñòâå ïîðîæäàþùåé äëÿ íåêîòîðîãî äðóãîãî ëèíåéíîãî êîäà (ï, ï-k), íàçûâàåìîãî äâîéñòâåííûì.
Êîäèðóþùåå óñòðîéñòâî äëÿ ëèíåéíîãî (ï,k) êîäà (ðèñ. íà ïðåäûäóùåé ñòð.) ñîñòîèò èç k-ðàçðÿäíîãî ñäâèãàþùåãî ðåãèñòðà è r=ï-k áëîêîâ ñóììàòîðîâ ïî ìîäóëþ 2. Èíôîðìàöèîííûå ñèìâîëû îäíîâðåìåííî ïîñòóïàþò íà âõîä ðåãèñòðà è íà âûõîä êîäèðóþùåãî óñòðîéñòâà ÷åðåç êîììóòàòîð Ê. Ñ ïîñòóïëåíèåì k-ãî èíôîðìàöèîííîãî ñèìâîëà íà âûõîäàõ áëîêîâ ñóììàòîðîâ â ñîîòâåòñòâèè ñ óðàâíåíèÿìè (7.11) ôîðìèðóþòñÿ ïðîâåðî÷íûå ñèìâîëû, êîòîðûå çàòåì ïîñëåäîâàòåëüíî ïîñòóïàþò íà âûõîä êîäåðà. Ïðîöåññ äåêîäèðîâàíèÿ ñâîäèòñÿ ê âûïîëíåíèþ îïåðàöèè
ãäå Â- âåêòîð, ñîîòâåòñòâóþùèé ïåðåäàâàåìîé êîäîâîé êîìáèíàöèè. Ïðè S=0 äåêîäåð ïðèíèìàåò ðåøåíèå îá îòñóòñòâèè îøèáîê, à ïðè S≠O - î íàëè÷èè îøèáîê. Ïî êîíêðåòíîìó âèäó ñèíäðîìà ìîæíî â ïðåäåëàõ êîððåêòèðóþùåé ñïîñîáíîñòè êîäà óêàçàòü íà îøèáî÷íûå ñèìâîëû è èõ èñïðàâèòü.
Äåêîäåð ëèíåéíîãî êîäà (ðèñ. íà ñëåäóþùåé ñòð.) ñîñòîèò èç k- ðàçðÿäíîãî ñäâèãàþùåãî ðåãèñòðà, (ï-k) áëîêîâ ñóììàòîðîâ ïî ìîäóëþ 2, ñõåìû ñðàâíåíèÿ, àíàëèçàòîðà îøèáîê è êîððåêòîðà. Ðåãèñòð ñëóæèò äëÿ çàïîìèíàíèÿ èíôîðìàöèîííûõ ñèìâîëîâ ïðèíÿòîé êîäîâîé ïîñëåäîâàòåëüíîñòè, èç êîòîðûõ â áëîêàõ ñóììàòîðîâ ôîðìèðóþòñÿ ïðîâåðî÷íûå ñèìâîëû. Àíàëèçàòîð îøèáîê ïî êîíêðåòíîìó âèäó ñèíäðîìà, ïîëó÷àåìîãî â ðåçóëüòàòå ñðàâíåíèÿ ôîðìèðóåìûõ íà ïðèåìíîé ñòîðîíå è ïðèíÿòûõ ïðîâåðî÷íûõ ñèìâîëîâ, îïðåäåëÿåò ìåñòà îøèáî÷íûõ ñèìâîëîâ. Èñïðàâëåíèå èíôîðìàöèîííûõ ñèìâîëîâ ïðîèçâîäèòñÿ â êîððåêòîðå. Çàìåòèì, ÷òî â îáùåì ñëó÷àå ïðè äåêîäèðîâàíèè ëèíåéíîãî êîäà ñ èñïðàâëåíèåì îøèáîê â ïàìÿòè äåêîäåðà äîëæíà õðàíèòüñÿ òàáëèöà ñîîòâåòñòâèé ìåæäó ñèíäðîìàìè è âåêòîðàìè îøèáîê. Ñ ïðèõîäîì êàæäîé êîäîâîé êîìáèíàöèè äåêîäåð äîëæåí ïåðåáðàòü âñþ òàáëèöó. Ïðè íåáîëüøèõ çíà÷åíèÿõ (ï-k) ýòà îïåðàöèÿ íå âûçûâàåò çàòðóäíåíèé. Îäíàêî äëÿ âûñîêîýôôåêòèâíûõ êîäîâ äëèíîé ï, ðàâíîé íåñêîëüêèì äåñÿòêàì, ðàçíîñòü (ï-k) ïðèíèìàåò òàêèå çíà÷åíèÿ, ÷òî ïåðåáîð òàáëèöû îêàçûâàåòñÿ ïðàêòè÷åñêè íåâîçìîæíûì. Íàïðèìåð, äëÿ êîäà (63, 51), èìåþùåãî êîäîâîå ðàññòîÿíèå d=5, òàáëèöà ñîñòîèò èç 2^12 = 4096 ñòðîê.
Çàäà÷à çàêëþ÷àåòñÿ â âûáîðå íàèëó÷øåãî (ñ ïîçèöèè òîãî èëè èíîãî êðèòåðèÿ) êîäà. Ñëåäóåò çàìåòèòü, ÷òî äî ñèõ ïîð îáùèå ìåòîäû ñèíòåçà îïòèìàëüíûõ ëèíåéíûõ êîäîâ íå ðàçðàáîòàíû.
Öèêëè÷åñêèå êîäû.
Öèêëè÷åñêèå êîäû îòíîñÿòñÿ ê êëàññó ëèíåéíûõ ñèñòåìàòè÷åñêèõ. Ïîýòîìó äëÿ èõ ïîñòðîåíèÿ â ïðèíöèïå äîñòàòî÷íî çíàòü ïîðîæäàþùóþ ìàòðèöó.
Ìîæíî óêàçàòü äðóãîé ñïîñîá ïîñòðîåíèÿ öèêëè÷åñêèõ êîäîâ, îñíîâàííûé íà ïðåäñòàâëåíèè êîäîâûõ êîìáèíàöèé ìíîãî÷ëåíàìè b(õ) âèäà:
Êàæäûé öèêëè÷åñêèé êîä (n, k) õàðàêòåðèçóåòñÿ òàê íàçûâàåìûì ïîðîæäàþùèì ìíîãî÷ëåíîì. Èì ìîæåò áûòü ëþáîé ìíîãî÷ëåí ð(õ) ñòåïåíè n-k. Öèêëè÷åñêèå êîäû õàðàêòåðèçóþòñÿ òåì, ÷òî ìíîãî÷ëåíû b(x) êîäîâûõ êîìáèíàöèé äåëÿòñÿ áåç îñòàòêà íà ð(õ). Ïîýòîìó ïðîöåññ êîäèðîâàíèÿ ñâîäèòñÿ ê îòûñêàíèþ ìíîãî÷ëåíà b(x) ïî èçâåñòíûì ìíîãî÷ëåíàì a(õ) à ð(õ), äåëÿùåãîñÿ íà ð(õ), ãäå a(õ)- ìíîãî÷ëåí ñòåïåíè k-1, ñîîòâåòñòâóþùèé èíôîðìàöèîííîé ïîñëåäîâàòåëüíîñòè ñèìâîëîâ.
ãäå m(õ)- ÷àñòíîå, à ñ(õ)- îñòàòîê. Òàê êàê îïåðàöèè ñóììèðîâàíèÿ è âû÷èòàíèÿ ïî ìîäóëþ 2 ñîâïàäàþò, òî âûðàæåíèå (7.12) ïåðåïèøåì â âèäå: (7.13)
Ìíîãî÷ëåí èìååò ñëåäóþùóþ ñòðóêòóðó: ïåðâûå n-k ÷ëåíîâ íèçøåãî ïîðÿäêà ðàâíû íóëþ, à êîýôôèöèåíòû îñòàëüíûõ ñîâïàäàþò ñ ñîîòâåòñòâóþùèìè êîýôôèöèåíòàìè èíôîðìàöèîííîãî ìíîãî÷ëåíà à(õ). Ìíîãî÷ëåí ñ(õ) èìååò ñòåïåíü ìåíüøå n-k. Òàêèì îáðàçîì, â íàéäåííîì ìíîãî÷ëåíå b(x) êîýôôèöèåíòû ïðè õ â ñòåïåíè n-k è âûøå ñîâïàäàþò ñ èíôîðìàöèîííûìè ñèìâîëàìè, à êîýôôèöèåíòû ïðè îñòàëüíûõ ÷ëåíàõ, îïðåäåëÿåìûõ ìíîãî÷ëåíîì ñ(õ), ñîâïàäàþò ñ ïðîâåðî÷íûìè ñèìâîëàìè. Íà îñíîâå ïðèâåäåííûõ ñõåì óìíîæåíèÿ è äåëåíèÿ ìíîãî÷ëåíîâ è ñòðîÿòñÿ êîäèðóþùèå óñòðîéñòâà äëÿ öèêëè÷åñêèõ êîäîâ.
 êà÷åñòâå ïðèìåðà ïðèâåäåíà ñõåìà êîäåðà è äåêîäåðà äëÿ êîäà (ñì. ðèñ.) ñ ïîðîæäàþùèì ìíîãî÷ëåíîì:
Ïðèíÿòàÿ êîäîâàÿ êîìáèíàöèÿ îäíîâðåìåííî ïîñòóïàåò â áóôåðíûé ðåãèñòð ñäâèãà, ñëóæàùèé äëÿ çàïîìèíàíèÿ êîäîâîé êîìáèíàöèè è äëÿ åå öèêëè÷åñêîãî ñäâèãà, è íà óñòðîéñòâî äåëåíèÿ íà ìíîãî÷ëåí ð(õ) äëÿ âû÷èñëåíèÿ ñèíäðîìà.  èñõîäíîì ñîñòîÿíèè êëþ÷ íàõîäèòñÿ â ïîëîæåíèè 1. Ïîñëå ñåìè òàêòîâ áóôåðíûé ðåãèñòð îêàçûâàåòñÿ çàãðóæåííûì, à â ðåãèñòðå óñòðîéñòâà äåëåíèÿ áóäåò âû÷èñëåí ñèíäðîì. Åñëè âåñ ñèíäðîìà áîëüøå åäèíèöû, òî äåêîäåð íà÷èíàåò ïðîèçâîäèòü öèêëè÷åñêèå ñäâèãè êîìáèíàöèè â áóôåðíîì ðåãèñòðå ïðè îòñóòñòâèè íîâîé êîìáèíàöèè íà âõîäå è îäíîâðåìåííî âû÷èñëÿòü èõ ñèíäðîìû s(x)ximodp(x) â óñòðîéñòâå äåëåíèÿ. Åñëè íà íåêîòîðîì 1-ì øàãå âåñ ñèíäðîìà îêàæåòñÿ ìåíüøå 2, òî êëþ÷ ïåðåõîäèò â ïîëîæåíèå 2, îáðàòíûå ñâÿçè â ðåãèñòðå äåëåíèÿ ðàçðûâàþòñÿ. Ïðè ïîñëåäóþùèõ òàêòàõ îøèáêè èñïðàâëÿþòñÿ ïóòåì ïîäà÷è ñîäåðæèìîãî ðåãèñòðà äåëåíèÿ íà âõîä ñóììàòîðà ïî ìîäóëþ 2, âêëþ÷åííîãî â áóôåðíûé ðåãèñòð. Ïîñëå ñåìè òàêòîâ ðàáîòû äåêîäåðà â àâòîíîìíîì ðåæèìå èñïðàâëåííàÿ êîìáèíàöèÿ â áóôåðíîì ðåãèñòðå âîçâðàùàåòñÿ â èñõîäíîå ïîëîæåíèå (èíôîðìàöèîííûå ñèìâîëû áóäóò çàíèìàòü ñòàðøèå ðàçðÿäû).
Ñóùåñòâóþò è äðóãèå, áîëåå óíèâåðñàëüíûå, àëãîðèòìû äåêîäèðîâàíèÿ.
Ê öèêëè÷åñêèì êîäàì îòíîñÿòñÿ êîäû Õýììèíãà, êîòîðûå ÿâëÿþòñÿ ïðèìåðàìè íåìíîãèõ èçâåñòíûõ ñîâåðøåííûõ êîäîâ. Îíè èìåþò êîäîâîå ðàññòîÿíèå d=3 è èñïðàâëÿþò âñå îäèíî÷íûå îøèáêè. Ñðåäè öèêëè÷åñêèõ êîäîâ øèðîêîå ïðèìåíåíèå íàøëè êîäû Áîóçà- ×îóäõóðè- Õîêâèíãåìà (Á×Õ).
Ñâåðòî÷íûå êîäû
Ìåòîäû îïèñàíèÿ ñâåðòî÷íûõ êîäîâ.
Êîäåð ÑÊ ñîäåðæèò ðåãèñòð ïàìÿòè äëÿ õðàíåíèÿ îïðåäåëåííîãî ÷èñëà èíôîðìàöèîííûõ ñèìâîëîâ è ïðåîáðàçîâàòåëü èíôîðìàöèîííîé ïîñëåäîâàòåëüíîñòè â êîäîâóþ ïîñëåäîâàòåëüíîñòü. Ïðîöåññ êîäèðîâàíèÿ ïðîèçâîäèòñÿ íåïðåðûâíî. Ñêîðîñòü êîäà R=k/n, ãäå k - ÷èñëî èíôîðìàöèîííûõ ñèìâîëîâ, îäíîâðåìåííî ïîñòóïàþùèõ íà âõîä êîäåðà, n - ÷èñëî ñîîòâåòñòâóþùèõ èì ñèìâîëîâ íà âûõîäå êîäåðà. Ñõåìà ïðîñòîãî êîäåðà ïîêàçàíà íà ðèñ. 1.1à.
Èíôîðìàöèîííûå äâîè÷íûå ñèìâîëû u ïîñòóïàþò íà âõîä ðåãèñòðà ñ Ê ðàçðÿäàìè. Íà âûõîäàõ ñóììàòîðîâ ïî ìîäóëþ 2 îáðàçóþòñÿ êîäîâûå ñèìâîëû a(1) è a(2). Âõîäû ñóììàòîðîâ ñîåäèíåíû ñ îïðåäåëåííûìè ðàçðÿäàìè ðåãèñòðà. Çà âðåìÿ îäíîãî èíôîðìàöèîííîãî ñèìâîëà íà âûõîäå îáðàçóþòñÿ äâà êîäîâûõ ñèìâîëà (R= 1/2). Âîçìîæíî êîäèðîâàíèå è ñ äðóãèìè ñêîðîñòÿìè. Ïðè ñêîðîñòè 2/3 íà âõîä êîäåðà îäíîâðåìåííî ïîñòóïàåò k=2 èíôîðìàöèîííûõ ñèìâîëà, íà âûõîäå ïðè ýòîì îáðàçóåòñÿ n=3 êîäîâûõ ñèìâîëà. Ñõåìà òàêîãî êîäåðà ïîêàçàíà íà ðèñ. 1.1,6.
Ðàññìàòðèâàåìûé êîä íàçûâàåòñÿ ñâåðòî÷íûì, ïîñòîëüêó ïîñëåäîâàòåëüíîñòü êîäîâûõ ñèìâîëîâ à ìîæåò áûòü îïðåäåëåíà êàê ñâåðòêà èíôîðìàöèîííûõ ñèìâîëîâ u ñ èìïóëüñíûì îòêëèêîì êîäåðà. Íà ðèñ. 1.2 ïîêàçàíî ïðîõîæäåíèå åäèíè÷íîé ïîñëåäîâàòåëüíîñòè u=100… ÷åðåç êîäåð.
Ñèìâîëû a(1) è a(2) íà åãî âûõîäå îáðàçóþò èìïóëüñíûé îòêëèê h= 00111011 00... Òàêèì îáðàçîì, åñëè íà âõîäå êîäåðà äåéñòâóåò ïðîèçâîëüíàÿ èíôîðìàöèîííàÿ ïîñëåäîâàòåëüíîñòü è, òî ïîñëåäîâàòåëüíîñòü íà åãî âûõîäå åñòü ñóììà ïî ìîäóëþ 2 âñåõ èìïóëüñíûõ îòêëèêîâ, îáóñëîâëåííûõ äåéñòâèåì ñìåùåííûõ âî âðåìåíè ñèìâîëîâ 1. Ñâåðòî÷íûé êîäåð, êàê àâòîìàò ñ êîíå÷íûì ÷èñëîì ñîñòîÿíèé, ìîæåò áûòü îïèñàí äèàãðàììîé ñîñòîÿíèé. Äèàãðàììà ïðåäñòàâëÿåò ñîáîé íàïðàâëåííûé ãðàô è îïèñûâàåò âñå âîçìîæíûå ïåðåõîäû êîäåðà èç îäíîãî ñîñòîÿíèÿ â äðóãîå, à òàêæå ñîäåðæèò ñèìâîëû âûõîäîâ êîäåðà, êîòîðûå ñîïðîâîæäàþò ýòè ïåðåõîäû.
Ïåðâîíà÷àëüíî êîäåð íàõîäèòñÿ â ñîñòîÿíèè 00, è ïîñòóïëåíèå íà åãî âõîä èíôîðìàöèîííîãî ñèìâîëà u=0 ïåðåâîçÿò åãî òàêæå â ñîñòîÿíèå 00. Ïðè ýòîì íà âûõîäå êîäåðà áóäóò ñèìâîëû a(1)a(2)=00. Íà äèàãðàììå ýòîò ïåðåõîä îáîçíà÷àåòñÿ ïåòëåé 00, âûõîäÿùåé èç ñîñòîÿíèÿ 00 è âíîâü âîçâðàùàþùåéñÿ â ýòî ñîñòîÿíèå. Äàëåå, ïðè ïîñòóïëåíèè ñèìâîëà u=1 êîäåð ïåðåõîäèò â ñîñòîÿíèå 10, ïðè ýòîì, íà âûõîäå áóäóò ñèìâîëû a(1)a(2)=11. Ýòîò ïåðåõîä èç ñîñòîÿíèÿ 00 â ñîñòîÿíèå 10 îáîçíà÷àåòñÿ ïóíêòèðíîé ëèíèåé. Äàëåå âîçìîæíî ïîñòóïëåíèå íà âõîä êîäåðà èíôîðìàöèîííûõ ñèìâîëîâ 0 ëèáî 1. Ïðè ýòîì êîäåð ïåðåõîäèò â ñîñòîÿíèå 01 ëèáî 11, à ñèìâîëû íà âûõîäå áóäóò 10 ëèáî 01 ñîîòâåòñòâåííî. Ïðîöåññ ïîñòðîåíèÿ äèàãðàììû çàêàí÷èâàåòñÿ êîãäà áóäóò ïðîñìîòðåíû âñå âîçìîæíûå ïåðåõîäû èç îäíîãî ñîñòîÿíèÿ âî âñå îñòàëüíûå.
Ðåøåò÷àòàÿ äèàãðàììà ÿâëÿåòñÿ ðàçâåðòêîé äèàãðàììû ñîñòîÿíèé âî âðåìåíè. Íà ðåøåòêå ñîñòîÿíèÿ ïîêàçàíû óçëàìè, à ïåðåõîäû ñîåäèíÿþùèìè èõ ëèíèÿìè. Ïîñëå êàæäîãî ïåðåõîäà èç îäíîãî ñîñòîÿíèÿ â äðóãîå ïðîèñõîäèò ñìåùåíèå íà îäèí øàã âïðàâî. Ðåøåò÷àòàÿ äèàãðàììà äàåò íàãëÿäíîå ïðåäñòàâëåíèå âñåõ ðàçðåøåííûõ ïóòåé, ïî êîòîðûì ìîæåò ïðîäâèãàòüñÿ êîäåð ïðè êîäèðîâàíèè. Êàæäîé èíôîðìàöèîííîé ïîñëåäîâàòåëüíîñòè íà âõîäå êîäåðà ñîîòâåòñòâóåò åäèíñòâåííûé ïóòü ïî ðåøåòêå. Ïîñòðîåíèå ðåøåòêè ïðîèçâîäèòñÿ íà îñíîâå äèàãðàììû ñîñòîÿíèé. Èñõîäíîå ñîñòîÿíèå S(1)S(2)=0. Ñ ïîñòóïëåíèåì î÷åðåäíîãî ñèìâîëà u=0 ëèáî 1 âîçìîæíû ïåðåõîäû â ñîñòîÿíèÿ 00 ëèáî 10, îáîçíà÷àåìûå âåòâÿìè 00 è 11. Ïðîöåññ ñëåäóåò ïðîäîëæèòü, ïðè÷åì ÷åðåç òðè øàãà î÷åðåäíîé ôðàãìåíò, ðåøåòêè áóäåò ïîâòîðÿòüñÿ. Ïóíêòèðîì ïîêàçàí ïóòü 11100001..., ñîîòâåòñòâóþùèé ïîñòóïëåíèþ íà âõîä êîäåðà èíôîðìàöèîííîé ïîñëåäîâàòåëüíîñòè 1011...
Çäåñü èíäåêñû â ñêîáêàõ îáîçíà÷àþò: i- íîìåð âõîäà êîäåðà, 1≤ j≤ n, j- íîìåð âûõîäà êîäåðà, 1≤i≤ k. Èíäåêñû áåç ñêîáîê (0, 1, 2, ...) îáîçíà÷àþò äèñêðåòíûå ìîìåíòû âðåìåíè.
ÑÊ ìîæíî òàêæå çàäàâàòü ïîðîæäàþùåé ìàòðèöåé (1.3):
Êàê ïðè èñïîëüçîâàíèè áëîêîâûõ êîäîâ, ïðîöåññ êîäèðîâàíèÿ ìîæåò áûòü ïðåäñòàâëåí â ìàòðè÷íîé ôîðìå: A=UG (1.4)
,ãäå U- ïîëóáåñêîíå÷íàÿ ìàòðèöà âõîäíûõ èíôîðìàöèîííûõ ñèìâîëîâ, À- ïîëóáåñêîíå÷íàÿ ìàòðèöà ñèìâîëîâ íà âûõîäå êîäåðà.
Äåêîäèðîâàíèå ñâåðòî÷íûõ êîäîâ.
Àëãåáðàè÷åñêèå ìåòîäû äåêîäèðîâàíèÿ îñíîâàíû íà èñïîëüçîâàíèè àëãåáðàè÷åñêèõ ñâîéñòâ êîäîâûõ ïîñëåäîâàòåëüíîñòåé.  ðÿäå ñëó÷àåâ ýòè ìåòîäû ïðèâîäÿò ê ïðîñòûì ðåàëèçàöèÿì êîäåêà. Òàêèå àëãîðèòìû ÿâëÿþòñÿ íåîïòèìàëüíûìè, òàê êàê èñïîëüçóåìûå àëãåáðàè÷åñêèå ïðîöåäóðû äåêîäèðîâàíèÿ ïðåäíàçíà÷åíû äëÿ èñïðàâëåíèÿ êîíêðåòíûõ (è íå âñåõ) êîíôèãóðàöèé îøèáîê â êàíàëå. Àëãåáðàè÷åñêèå ìåòîäû îòîæäåñòâëÿþò ñ ïîýëåìåíòíûì ïðèåìîì ïîñëåäîâàòåëüíîñòåé, êîòîðûé äëÿ êîäîâ ñ èçáûòî÷íîñòüþ, êàê èçâåñòíî, äàåò õóäøèå ðåçóëüòàòû, ÷åì ïðèåì â öåëîì.
Âåðîÿòíîñòíûå ìåòîäû äåêîäèðîâàíèÿ çíà÷èòåëüíî áëèæå ê îïòèìàëüíîìó ïðèåìó â öåëîì, òàê êàê â ýòîì ñëó÷àå äåêîäåð îïåðèðóåò ñ âåëè÷èíàìè, ïðîïîðöèîíàëüíûìè âåðîÿòíîñòÿì, îöåíèâàåò è ñðàâíèâàåò âåðîÿòíîñòè ðàçëè÷íûõ ãèïîòåç è íà ýòîé îñíîâå âûíîñèò ðåøåíèÿ î ïåðåäàâàåìûõ ñèìâîëàõ.
Ïîðîãîâîå äåêîäèðîâàíèå.
Âåðîÿòíîñòíûå ìåòîäû äåêîäèðîâàíèÿ äîñòàòî÷íî ñëîæíû â ðåàëèçàöèè, õîòÿ è îáåñïå÷èâàþò âûñîêóþ ïîìåõîóñòîé÷èâîñòü. Íàðÿäó ñ íèìè øèðîêî ïðèìåíÿþò áîëåå ïðîñòûå àëãîðèòìû. Äëÿ ýòîé öåëè èñïîëüçóþò êëàññ ÑÊ, äîïóñêàþùèõ ïîðîãîâîå äåêîäèðîâàíèå.
Ñõåìà êîäåêà íà ðèñóíêå. Ìîäåëüþ äâîè÷íîãî êàíàëà ÿâëÿþòñÿ ñóììàòîðû ïî
ìîäóëþ 2, íà âõîäû êîòîðûõ, êðîìå êîäîâûõ ïîñëåäîâàòåëüíîñòåé à(1) è à(2), ïîñòóïàþò îøèáêè å(1) è å(2). Äåêîäåð ñîäåðæèò àíàëîã êîäåðà, â êîòîðîì ïðèíÿòûì ñèìâîëàì ôîðìèðóåòñÿ êîïèÿ ïðîâåðî÷íîé ïîñëåäîâàòåëüíîñòè.  ôîðìèðîâàòåëå ñèíäðîìà (ñóììàòîðå ïî ìîäóëþ 2) îáðàçóåòñÿ ïîñëåäîâàòåëüíîñòü ñèíäðîìîâ, êîòîðàÿ ïîñòóïàåò íà âõîä ñèíäðîìíîãî ðåãèñòðà. Íàáîðàì îøèáîê ñîîòâåòñòâóþò îïðåäåëåííûå êîíôèãóðàöèè ñèíäðîìîâ ïîñëåäîâàòåëüíîñòè S. Åñëè êîëè÷åñòâî íåíóëåâûõ ñèíäðîìîâ ïðåâûøàåò îïðåäåëåííûé ïîðîã, íà âûõîäå ïîðîãîâîãî ýëåìåíòà ïîÿâëÿåòñÿ ñèìâîë êîððåêöèè, êîòîðûé â êîððåêòîðå èñïîëüçóåòñÿ äëÿ èñïðàâëåíèÿ îøèáêè â èíôîðìàöèîííîì ñèìâîëå.
Ñïèñîê èñïîëüçîâàííîé ëèòåðàòóðû:
1. Ðàäèîòåõíè÷åñêèå ñèñòåìû ïåðåäà÷è èíôîðìàöèè, ïîä ðåä. Â. Â. Êàëìûêîâà
2. Ñâåðòî÷íûå êîäû â ñèñòåìàõ ïåðåäà÷è èíôîðìàöèè, ó÷åáíîå ïîñîáèå
Êàôåäðà Ðàäèîòåõíè÷åñêèõ Ñèñòåì ðåôåðàò ïî èçáûòî÷íûì êîäàì Ïðåïîäàâàòåëü: Ñìåðäîâà Í. Å. Ãðóïïà: ÐÒ 9505 Ñòóäåíò: Ìàòâååâ À. Í. Äàòà ñäà÷è: Ìàé 1999 ãîäà. Ìîñêâà, 1999 ã. Âñòóïëåíèå.
Ýôôåêò Ãàííà è åãî èñïîëüçîâàíèå, â äèîäàõ, ðàáîòàþùèõ â ãåíåðàòîðíîì ðåæèìå
Ëàçåðíàÿ áåçîïàñíîñòü
Èñòîðèÿ ðàçâèòèÿ ñîòîâîé ñâÿçè
Ôîòîðåçèñòîðû
Âîëîêîííî-Îïòè÷åñêèå Ëèíèè Ñâÿçè
Öâåòíàÿ ñòåðåîòåëåâèçèîííàÿ êàìåðà
Ýëåêòðè÷åñêèå ôèëüòðû
Ñïîñîá îïðåäåëåíèÿ æèâó÷åñòè ñâÿçè (âåðîÿòíîñòè ñâÿçíîñòè)
Ðàäèîðåëåéíàÿ ñâÿçü
Âëèÿíèå ãèñòåðåçèñà è âèõðåâûõ òîêîâ íà òîê êàòóøêè ñ ôåððîìàãíèòíûì ñåðäå÷íèêîì
Copyright (c) 2024 Stud-Baza.ru Ðåôåðàòû, êîíòðîëüíûå, êóðñîâûå, äèïëîìíûå ðàáîòû.