Қателердiң байланыстың техникасындағы табылу

Қателердi табу және дұрыстау 
 

Қателердiң байланыстың  техникасындағы табылу - байланыс тораптары бойынша мәлiметтiң жазылуы немесе оның берiлуiнiң жанында  мәлiмет бүтiндiгiнiң бақылау бағытталған әсер. (қателердiң коррекциясы) қателердiң дұрыстауы - мәлiметтiң қалпына келтiруiн процедура оның сақтауды құрылым немесе байланыс каналынан оқуынан кейiн.

 Қателердi табу үшiн қателердiң табылулары кодтарды пайдаланады, түзету үшiн - (кодтар, түзетушi қателер, коррекциясы бар код қателер, кедергiге шыдамды кодтар) түзететiн кодтар.

Байланыс желiлерi бойынша мәлiметтi сақтауды процессте және мәлiметтiң берiлулерi қателер сөзсiз пайда болады.  

Қателермен күресу әдiстерi 

Қателердiң мәлiмет бүтiндiгiнiң бақылауы және дұрыстауы - (OSIнiң торлық үлгiсiнiң физикалық, жыралық, көлiк деңгейлерi жеке алғанда) мәлiметi бар көп жұмыс деңгейлерiне маңызды есептерi.

Байланыс жүйелерiнде қателермен күрестiң бiрнеше стратегиялары болуы мүмкiн: 

   * мәлiметтердiң блоктерiндегi қателерiнiң табылуы және бұл жолдың майып блок-лердiң қайтадан тапсыруын автоматты сұрау салу * жыралық және көлiк деңгейлерде қолданылады;

   * мәлiметтердiң блоктерiндегi қателерiнiң табылуы және мұндай жолдың майып блок-лерiнiң лақтырып тастауы * берiлудi тоқтау маңызды және қайтадан тапсыруға уақыт жоқ болатын ағынды мультимедиа жүйелерiндегi кейде қолданылады;

    *(forward error correction ағылшынша) қателердiң  дұрыстауы физикалық деңгейде қолданылады. 
 

Қателердiң табылудың кодтары және түзетуi 

Түзететiн кодтар - бөгеуiлдi ықпалмендi мәлiметтiң берiлуiнiң жанында пайда болатын қателердiң табылу немесе түзетуi үшiн кодтар, қызметшiлер, сонымен бiрге оның сақтауында.

Пайдалы мәлiметтерде ол үшiн (берiлуге ) жазған кезде жiктелген (бақылау саны) мол мәлiмет арнайы түрлермен толықсытады, (қабылдау ) оқуда ол қатенi бiлдiрiп немесе жөнделу үшiн сол үшiн қолданады. Жөндеуге болатын қателердiң саны белгiлi шектелген және нақты қолданылатын кодтан тәуелдi болады.

 Kодтармен, түзетушi түзетушi қателер, қателердiң табылуының кодтары тығыз байланған. Айырмашылыққа бiрiншi, соңғы тек қана тапсырған мәлiметтердегi қатенiң бар болуын айғақ орната алады, бiрақ оны жөндемеу.

Шындықта, қателердiң табылуының қолданылатын кодтары кодтар кодтардың сыныптары, нелер сонымен бiрге жатады, түзетушi. Iс жүзiнде, қате түзетушi кез келген код сонымен бiрге бола алады (ол сонымен бiрге жөндеуге қарағанда қателердiң саны көбiрек бiлдiредi) қателердiң табылуы үшiн қолдану.

Осы кодтары бар жұмыстар әдiс бойынша, түзетушi түзетушi қателер тұрақты ұзындықтың бөлiктерi және өңделетiн олардың әрқайсыларына мәлiметтi жеке бөлетiн блокке және лек-легiмен ретiнде жұмыс iстейтiн свёрточныелерге жiктеледi.

Блок кодтары

Кодпен жазылатын мәлiмет мейлi бит n ның ұзындығының кодтық сөздерiнде өзгертетiн бит k ұзындығының бөлiктерiне жiктеледi.

Блок кодын берiлсiн әртүрлi мүмкiн, соның iшiнде ақпараттық биттердiң k әрбiр жиынтығы кодтық сөздiң битi n безбенделетiн кестемен. Жақсы код алайда, қалай минимум болғанын қанағаттандыруы керек, келесi белгiлерге:

    * қабiлеттiлiк қателердiң саны көбiрек сияқты дұрыстау мүмкiн,

    сияқты * кiшi артықшылық мүмкiн,

    * кодтау және қайта кодтауды оңайлық.

Келтiрiлген талаптар бiр-бiрiне қайшы келетiнiн көруге қиын емес. Сондықтан тап әрбiрi есептердiң өз шеңберi үшiн жарамды кодтардың үлкен саны бар болады.

Түгелдей дерлiк қолданылатын кодтар сызықты болып табылады. Бұл сызықты емес кодтарды зерттейтiн, және қиын олар үшiн ©пд§гұн және қайта кодтауды қолайлы жеңiлдiктi қамтамасыз етуге едәуiр күрделiрек болатын байланған.

Тұтас көрiнiстiң сызықты кодтары

Сызықты блок коды - k изоморфты кеңiстiгiне мұндай оның кодтық сөздерiнiң жиыны kты құрастырады - nға (оның C деп  атаймыз) бiр қалыпты сызықты iшкi кеңiстiк - бiр қалыпты сызықты кеңiстiк ретiнде код - биттiк векторлар.

Бұл демек, Gның тудыратын матрица деп аталатын азғындалмаған матрицасына биттiк вектор кодтауды операция бастапқы kтарды көбейтуге сәйкес келетiн.

Ең төменгi қашықтық және түзететiн қабiлеттiлiк

   Негiзгi бап: Хемминг қашықтығы

Екi кодтық сөздердiң арасындағы   және (Хемминга метрикамен) Хемминга қашықтықпен және тиiстi позицияларға өте жақсы биттерiнiң саны деп аталады:

     ( , )=

=min( , )

сызықты блок кодының маңызды мiнездемесi болып табылады. Оның қаншалықты көрсетедi кодтар бiр-бiрiмен қашық орналастырған. Ол басқа анықтайды, мiнездеменi маңыздырақ - түзететiн қабiлеттiлiктi: 

  t= 

Хэмминг кодтары

Хэммингтiң кодтары - өте белгiлi және өздiгiнен тексерiлетiннiң және өздiгiнен коррекцияланатын кодтардың алғашқысы. Қарай екiлiк есептеу жүйесiне олар құрастырылған.

 Тарихы

Ричард Хэммингтi 1940-шi жылдардың ортасында Bell Model Vтың есептiк машинасында атақты Белл лабораторияларында жұмыс iстедi. Бұл жылдамдығы болды ап-аласа релелiк блок қолданушы электромеханикалық машина болды: бiр айналым бiрнеше секундте. Мәлiметтер машинаға перфокарталар арқылы жүргiзiлдi, және сондықтан оқу процессiнде қателерде жиi болды. Жұмыс күндерiнде табылған қателердi ашып дұрыстау үшiн арнайы кодтарды қолданылды шырақтардың сәуле таратуы бойынша қате туралы бұл операторда таныды, машинаны дұрыстап iске қосты. Операторлар болмайтында демалыс күндерiнде басқа машина қатенiң пайда болуында автоматты программадан шығып iске қосты.

Хэмминг демалыс күндерiнде жиi жұмыс iстедi, және көбiне-көп қозды, өйткенi перфокарталардың сенiмсiздiгi артынан өз бағдарламасын қайта жүктеуге жиi тиiстi болды. Ол бiрнеше жылдардың бойысында қателердiң түзетудiң тиiмдi алгоритмдарын құрастырудың үстiнде уақыт көп өткiздi. Ол 1950 жылда Хэммингтiң коды ретiнде бүгiнгi күн әдiс жариялады.

Жүйелi түрдегі кодтар

Жүйелi түрде кодтар арасында үлкен топты (қай барлық нышандарда тексеру және ақпараттыққа бөлуге болады) код бөлiнетiн блоктық құрастырады. Жүйелi түрде кодтардың ерекшелiгi тексеру нышандары ақпараттық нышандардың үстiнде нәтижеде сызықты операциялары ЄдЄйтын болып табылады. Бұдан басқа, кез келген шешiлген кодтық комбинация сызықты тәуелсiз кодтық комбинациялардың жиынының үстiнде нәтижеде сызықты операциялары алына алады.

Кодтар өздiгiнен тексерiлетiндер

Демек, Хэммингтiң кодтары деректердi берудiң жанында қате автоматты ашуға мүмкiндiк беретiн кодтармен кодтармен өздiгiнен тексерiлетiндермен болып табылады. Мысалы, олардың құрастыруы үшiн (бақылау ) бiр қосымша екiлiк дәреженi әрбiр сөзге қосып жазып және бiрлiктердiң кез келген санның суретiндегi жалпы сан жұп болатындай етiп бұл дәреженiң цифрын таңдауға жеткiлiктi. Мүмкiн, берiлетiн (соның iшiнде және тексеру ұшқынында) сөздiң дәрежесi жеке қателiк қандай болмасын бiрлiктердiң жалпы санының жұптығын өзгертедi. Модул бойынша санның екiлiк цифрларының арасында болатын бiрлiктердiң саны қателердiң бар болуы туралы белгi бере алады есептейтiн 2 есептеуiштер .

Демек, сонымен бiрге мүмкiн емес және ол жөндеу мүмкiндiгi жоқ дәреженiң өзiнде қате пайда болатынын бiлу. Төрт немесе дәрежелердiң жұп санында тiптiдегi бiр уақытта екi пайда болатын қателерi сонымен бiрге көзге түспеген болып қалады. Дегенмен, екi есе шығын, әсiресе төрт еселi қателер күмән арқа сүйейдi.

Өздiгiнен коррекцияланатын кодтар

Қателердiң автоматты дұрыстауы болуы мүмкiн кодтар деп аталады өздiгiнен коррекцияланатын. Жеке қателiктердiң дұрыстау өлшеулi өздiгiнен коррекцияланатын кодтың құрастырулары үшiн, бiр бiр тексеру ұшқыны жеткiлiксiз. Көрiнгендей ары қарай, kтың тексеру ұшқындарының саны теңсiздiк қанағаттанатындай етiп таңдауы керек

       k+m  немесе   k(k+m+1)  m-кодтық сөздiң негiзгi екiлiк дәрежелерiнiң саны. Mның мәндерiнiң бұл теңсiздiкпен сәйкес табылған тап қалған күйiнделер kтың ең төменгi мәнi кестеде келтiрiлген. 

 

Мүлде дәл қазiр ең үлкен екiлiк блоктық түзететiн кодтарды ұсынады. Бiрдей ұзындықтың блоктерiнiң түрiнде және әрбiр блок мұндай мәлiметтiң кодтарының қолдануында берiледi тәуелсiз бiр-бiрiмен кодпен жазып кодын табады. Барлық блоктық кодтардағы нышандары дерлiк ақпараттық және тексеруге бөлуге болады. Сайып келгенде, кодтарының барлық комбинациялары бөлiнедi тыйым салынған, (ақпараттық және тексеру нышандарының қай байланыстары үшiн болуы мүмкiн) шешiлген.

Каскадты кодтау. Итератив қайта кодтауы

Кодтаудың әртүрлi әдiстерiнiң артықшылықтары каскадты кодтау қолданып топтастыруға болады. Бiр кодпен бұл мәлiметте бастапқыда кодпен жазады, содан соң басқа, код нәтижеде пайда болады.

Мысалы, әйгiлi келесi конструкция болып табылады: мәлiметтер Рида-Соломонның кодтарымен кодпен жазады, содан соң кодпен свёрточнымдарды (бұл нышандарда жақын орналасқан қашық бiр-бiрiмен жайғастырылады) кезектестiрiп кодпен жазады. Қабылдағышта код свёрточныйды бастапқыда кодын табады, содан соң (қателердiң декодердiң свёрточногосы шығуында бұл пәшкеде Рида-Соломонның кодының әртүрлi кодтық сөздерi бiр нәрсеге тиедi) керi перемежение iске асады, және содан соң Рида-Соломонның кодының қайта кодтауы iске асады.