Лекция Құпиялау теориясы Кодталу теориясының негізгі ұғымдары және анықтамалары Алфавиттік кодтталу. Оптимал кодталу. Қателерді табу және өңдеу кодттары
жүктеу/скачать 198,4 Kb.
|
15-лекция
| Теорема. Σ сұлбалы алфавиттік кодталу өзара бір мәнділік қасиетіне ие болмайды сонда, тек сондағана, қашан Г(Σ) граф λ төбе арқылы өтетін бағытталған циклға ие болса.
Дәлелдеуі [5]. Сонымен теорема негізінде осындай алгаритмнің бар болуы Г(Σ) графтың құрылуынан және λ арқылы өтетін бағытталған циклды анықтаудан тұрады екен. Мысал: Төмендегідей сұлба бойынша алфавиттік кодталуды қарастырамыз: a1−−−b1b2 a2−−−b1b3b2 a3−−−−b2b3 (Σ) a4−−−−−b1b2b1b3 a5−−−−−−b2b1b2b2b3. Кезектегідей жіктеулерге иеміз: B1 = (b1) (b2), В2 = (b1) (b3 b2) = (b1 b3) b2, B3 = (b2) (b3), B4 = (b1) (b2 b1 b3) = (b1 b2 ) (b1 b3) = (b1 b2 b1)(b3), B5 = (b2)(b1b2b2b3 ) (b2)( b1b2 ) (b2b3) = (b2b1)( b2b2b3) = (b2b1b2)( b2b3)= = (b2b1 b2b2) (b3) . Бұл жерде B0 = {λ, b2, b1b3} және олармен B2 = (b1 b3) (b2), B4 = (b1b2) (b1 b3) =B1 ( b1b3), B5 =(b2)(b1 b2 )(b2 b3 ) =(b2) B1 B3 жіктеулер байланысты. Ал, ол Г(Σ) графты құруға мүмкіндік береді ( 4- сызба) λ O B1B3 B1 λ
4-сызба Г(Σ) граф екі В = (B1b1b3) (b2B1B3), яғни A′ = a4a5, В = B1(b1b3b2) B1B3, яғни A" = a1a2 a1a3 ашиалауға ие болған В = B1b1b3b2 B1B3 сөзді келтіріп шығаратын бағытталған циклға ие. Мысал. Кезектегідей сұлбаға ие болған алфавиттік кодталуларды қарастырамыз: a1−−−b1, a2−−−b2b1, a3−−−b1b2b2, a4−−−−b2b1b2b2, a5−−−−−b2b2b2b2. Олар үшін төмендегідей жіктеуге ие боламыз: B2 = (b2) b1= b2 B1; B3 = (b1) (b2b2) = B1(b2b2); B3 = (b1b2)( b2); B4 = (b2) (b1) (b2b2) = (b2)B1(b2b2); B4 = (b2)(b1b2b2) = b2b3; B4 = (b2 b1) (b2 b2) = B2(b2 b2); B4 = (b2 b1 b2)(b2); B5 = (b2) (b2 b2 b2 ) = ( b2 b2)( b2 b2) = (b2 b2 b2 )(b2). Мұнда В0 ={λ, b2, b2 b2, b2 b2 b2} және олармен B2 = b2 B1; B3 = B1(b2b2); B4 = (b2) B1(b2b2); B4 = b2 B3 ; B4 = B2(b2b2); B5 = (b2) (b2 b2 b2 ) = ( b2 b2)( b2 b2) = (b2 b2 b2 )(b2). жіктеулер байланысты. Біз λ төбе арқылы өтетін бағытталған циклға ие болмаған Г(Σ) граф аламыз ( 5- сызба ). λ b2b2 O B1 B2 B1 λ O B1 B3 λ O O b2b2b2 b2 λ 5-сызба
жүктеу/скачать 198,4 Kb. Достарыңызбен бөлісу:
|