Блоктық кодтар
ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ
Қазақ ұлттық техникалық университеті
Техникалық кибернетика кафедрасы
КУРСТЫҚ ЖҰМЫС
Тақырыбы Кедергіге тұрақты кодтау
Оқытушы
Ибрагимова Ә
Студент Асқаров М
Мамандығы 050704
Тобы КСУ-04-1қ
Алматы 2006
Мазмұны
1. Кіріспе................................................................................................................3
2. Канал арқылы ақпаратты тасымалдау.............................................................4
3. Каналдың ақпараттық моделі...........................................................................4
4. Мәліметті кодтау...............................................................................................7
5. Кедергіге қарсы кодтау.....................................................................................9
6. Блоктық кодтар ................................................................................................10
7 Артықты қолданудың жалпы принципі.........................................................12
8. Кодтың коррекциялаушы қабілеттігі кодтық қашықтықпен
9. Блоктық коррекциялаушы кодтардың геометриясы...................................16
10.Қортынды..........................................................................................................18
11.Қолданылған әдебиеттер тізімі.......................................................................19
Кіріспе
Менің курстық жұмысымда негізігі қарастырылатын мәселе кедергіге қарсы
Бұл жұмыс көп саларда қолданылады, мысалы радиотехникада, электроникада
Канал арқылы ақпаратты тасымалдау
Ақпаратты тасымалдау каналы байланыс желісінен, модулятор және демодулятордан
Шешімді қабылдаушы P және P– құрылғылары күмәнді сигналдарды
p ықтималдығына ие бөлек сигналда сақталатын ақпарат мөлшері
Бұл шарттардың бірінің орындалмауы ақпарат мөлшерінің кемуіне алып
Кедергілердің сипаты және деңгейі белгілі жағдайда тасымалдаудың сенімділігін
Каналдың ақпараттық моделі
Ақпараттық мүмкіндіктерді анализдеу үшін 1-суретте келтірілген байланыс каналының
ξ
Z
ЛС
Байланыс каналының мәліметтік каналы
Кедергілер кездейсоқ сипатқа ие және статистикалық заңдарға бағынады.
Канал арқылы ақпараттың өнімді түрде берілуін ұйымдастыру үшін
Егер кедергілер деңгейі аз және сигналдың бүлінуін ескермеуге
Ақпараттың дискретті көзі хабарлар құрылатын Z=(z1, z2, …,
П1 түрлендіргіші z хабарларын басқа алфавит X=(x1 x2,
Үздіксіз хабар жағдайында П1 түрлендіргіші үзіксіз сигналдың статистикалық
Каналдың ең маңызды сипаттамаларының бірі берілген канал бойымен
C=۟νxmax{I(Y, X)}.
Мұнда νx арқылы канал арқылы элементарлық сигналдарды тасымалдаудың
νx=1/τx.
Барлық тасымалданатын символдардың бірдей ұзақтығы τx жағдайында τx=τx.
{I(Y, X)} арқылы қабылданған сигналдың бір символында болатын
I(Y, X)=H(X)-H(X | Y),
мұндағы H(X) – қабылдаудың алдындағы тасымалданатын сигналдың орташа
Бұдан көрініп тұрғандай, символ сақтайтын ақпараттың орташа мөлшері
νx жылдамдығы тек канал қасиеттерімен анықталады және сигналдар
Сонымен, өткізгіштік қабілет тек каналдың өзіне ғана байланысты
Хабарларды тасымалдауды келесі канал түрлері үшін қарастырайық: кедергісіз
Мәліметті кодтау
Төменде қарастырылатын мәлімет кодтаудың жалпы түсінігі жүйе үшін
Бірақ есептей отырып, дискретті хабарлама әріптерден құралады,
Әріп хабарламаның құру үрдісі бірнеше мақсатта қолданылады.
Солардың бірі (Кодер Қоры КҚ) мынандай кодтау
Екінгші кодтаушы құралы көмегімен (Кодер Каналы КК) жіберілер
Сонымен кодтау және декодтау таңдау құрылғылары хабарлама қорының
Кодер каналынан кейін (КК)кғодталған сигнал сигналды кодталған
Алынған модулятор сигналы х нақты сызық байланысына беруге
Байланыс сызығында сигналға кедергілер каналды сондықтан декодтау
Кедергіге қарсы кодтау
Кедергіге тұрақты кодтау Шенноның №2 теоремасы (кедергісі бар
Каналдың өткізу қабілетінен кем ақпарат көзінің кез келген
Бұл символдар тізбегін беретін артықты кодтау кезіндегі
Қазіргі кезде кездесетін көптеген кедергіге қарсы кодтарда көрсетілген
Алгебралық кодтардың 2 үлкен класқа бөлінеді:
Блоктық;
Үздіксіз.
Блоктық кодтар: Хабардың әр әрпіне символдан тұратын
Блоктық кодтар бөлінетін және бөлінбейтін болады.
Бөлінбейтін кодтардың айырмашылығы символдардан шығу тізбегінде
Үздіксіз (бұтақ тәріздес) деп артықтық символдарды ақпараттық
Үздіксіз кодтар да бөлінетін және бөлінбейтін
Шулы бар бар дискретті канал үшін Шеннон
Көріп отырғанамыздай, теоремада көрсетілген идеалды берілетін кодты құру
Кодтау қабылданған сигналдың, яғни осыған символдар тізбегінің
Бұл кодтауды қосымша шарттардың тексерілген кезде алушы
Мұндай қасиеттерге ие кодтар―кедергіге қарсы кодтар деп аталады.
Қазіргі кезде белгілі кедергіге қарсы кодтардың көбіне
Алгебралық кодтарды екі ірі класқа бөлуге болады:
Блоктық кодтау жағдайында, кодтау порцедурасы әр әріпке (немесе
Блоктық көз барлық әріптер үшін n тұрақты
Бөлшектелетін және бөлшектелмейтін блоктық кодтар бар.
Бөлшектелмейтін кодтармен кодтаған кезде шығыс тізбектерді
Үздіксіз деп―кодталатын ақпатраттық символдар тізбегіне артық
Блоктық кодтар
Кодтың қателерді тауып, түзету қабілеті
Кедергілер әсер етуіне байланысты әр 2k рұқсат
Барлық мүмкін болатын беру жағдайларының табылатын
2n-2k =1-2n
2n
Қателерді түзету жағдайын қарастырайық. Декодтаудың кез келген
Кодтық комбинациядағы бұрмаланған символдардың санын
Кодтық коррекциялаушы мүмкіндіктерінің кодтық ара
Кез келген екі кодтық комбинацияларыдың айырмашылық дәрежесі
(Екілік кодтың екі комбинациясының арасындағы кодтық
Мысалы: 01001111101
1100001010
0101110111, d=7
Кодтық комбинациялардың рұқсат етілген кодтық барлық параметрлері
Декодтау максималды шын тәрізді әдісі бойынша
r қателерін табу үшін d0>r+1 талап етіледі;
Барлық қысқалық қателерін S-ке дейін түзету үшін
Барлық S қысқалық қателерін түзету және
қысқалық қателерің табу үшін r+S+1≤ d0.
Коррекциялаушы кодтың сапасын көрсеткіші-артықтық.
Rn=(n-k)/n
немесе Rk=(n-k)/k
мұндағы n – кодтың жалпы ұзындығы; k–ақпараттық разрядтың
Оптималды деп артықтықтың минималды болуына берілген
үшін d=3 минималды кодтық ара қашықтықы
Артықты қолданудың жалпы принципі
Кодтың табу қабілеті және қателерді түзеу артық
Барлығы 2k әртүрлі ену тізбегі және
А1
Аi
Aj
A2k
1-Сурет Мүмкін трансформация рұқсат кодтық комбинация кедергі
Сондықтан әрбір 2k рұқсат комбинация кедергі
2k мәні қатесіз жіберілуі (1-суретте жирныймен белгіленген)
2k(2k-1) рұқсат етілмеген комбинацияға өту, яғни
2k (2n-2k) рұқсат етілмеген комбинацияға өту, анықталуы мүмкін
Анықталатын қате кодтың комбинация бөлігі жалпы
2n-2k =1-2k
2n
Қарастырайық, мысалы кодтың анықтау қабілеті , әрбір
Кодтау кезінде әрбір k мәліметтің сатысында символдар
1- 2k =1/2
2k+1
Барлық оқиға саны басқа тиым
құрайды. Осыған орай , артықшылығы кезінде кез-келген
2n-2k =1/
2n (2n-2k)
Разбиения әдісі жиін ішінде мынаған байланысты, қандай қателер
Қазіргі уақыттта дейін көптеген өңделген кодтар пакет
Тәуелсіз байланысты қателерді былай анықтауға болады,
Қатенің кратності деп-кодтың комбинацияда символдар бұғатталу
Тәуелсіз қате байланысты қателер ықтималдығы n-разрядты кодтың
pr=Cnr pr (1-p)n-r
Етер еспетейтің болса, р
Канал арқылы ақпаратты тасымалдау
Кодтау әдістерінің классификациясы
Сандық информацияны кодтау
Көліктік байланыс туралы жалпы мәлімет
Сызықты топтық кодтар
ТОБЖ желілік кодтары
Ақпаратты қорғаудың криптографиялық әдістері
Фейстеля желісі
Криптография тарихы
Ауыстыру шифрлары