Döngüsel kodlar, belirli bir kodun bir kod sözcüğünün tüm sembollerinin döngüsel permütasyonu sırasında, aynı kodun başka bir kod sözcüğünün oluşmasıyla karakterize edilir.

Döngüsel kod kombinasyonu;

Ayrıca döngüsel kodun bir kombinasyonu.

Döngüsel kodlar göz önüne alındığında, ikili sayılar, derecesi ( NS - 1), NS- kod kelimesinin uzunluğu.

Örneğin, 1001111 kombinasyonu ( n = 7) bir polinom ile temsil edilecektir

Bu gösterimle, kod kombinasyonlarındaki eylemler, polinomlardaki eylemlere indirgenir. Bu eylemler, bu tür terimlerin indirgenmesinin modulo 2 yapılması dışında, sıradan cebire göre gerçekleştirilir.

Döngüsel bir kod kullanarak hata tespiti, izin verilen kombinasyonların önceden seçilmiş bazı polinomlarla kalansız bölünebilen kombinasyonlar olmasıyla sağlanır. G(x). Kabul edilen kombinasyon çarpık semboller içeriyorsa, polinom ile bölme G(x) kalanı ile gerçekleştirilir. Bu, bir hatayı belirten bir sinyal üretir. polinom G(x)adı verilen jeneratör.

Döngüsel kodun kombinasyonlarının oluşturulması, orijinal kombinasyonun çarpılmasıyla mümkündür. A(NS) üreteç polinomunda G(x) benzer terimlerin azaltılması ile modulo 2:

• ürünün en yüksek derecesi ( NS - 1), o zaman ortaya çıkan polinom, döngüsel kodun kod kombinasyonunu temsil edecektir;
• ürünün en yüksek derecesi şundan büyük veya ona eşitse NS, daha sonra ürün polinomu önceden seçilmiş bir derece polinomuna bölünür. NS ve çarpmanın sonucu, bölmenin kalan kısmıdır.

Böylece, döngüsel kodun kombinasyonlarını temsil eden tüm polinomlar aşağıdaki derecelere sahip olacaktır. NS.

Çoğu zaman, bölme işleminin gerçekleştirildiği polinom, polinomdur. G(x)= +1. Bu kod kombinasyonları oluşumu ile bilgi ve kontrol sembollerinin konumları önceden belirlenemez.

Döngüsel kodların büyük bir avantajı, yapılarında geri beslemeli kaydırmalı yazmaçları temsil eden kodlayıcılar ve kod çözme cihazları oluşturmanın basitliğidir.

Kayıt bitlerinin sayısı, üreten polinomun derecesine eşit olacak şekilde seçilir.

Geri besleme, sayıları üreten polinomun sıfır olmayan terimlerinin sayısından bir eksik olarak seçilen toplayıcılar aracılığıyla bazı bitlere yazmaç çıktısından gerçekleştirilir. Toplayıcılar, üreten polinomun sıfır olmayan terimlerinin karşılık geldiği kayıt bitlerinin girişlerine kurulur.

Şekil 17, dört bitlik bir deseni yedi bitlik bir desene dönüştürmek için kodlama kaydının bir diyagramını gösterir.

Şekil 17 - Kodlama kaydının şeması

Tablo Şekil 4, 1010011 çevrimsel kod kombinasyonunun, orijinal model 0101'in kaymalarıyla nasıl elde edildiğini gösterir. n = 7, k= 4. 0101 kombinasyonu, anahtar 1. konumdadır. İlk dört saat döngüsü sırasında kayıt doldurulur, ardından anahtar 2. konuma taşınır. Geri besleme kapatılır. Yedi değişen saat döngüsünün etkisi altında, yedi bitlik bir döngüsel kod oluşur.

Tablo 4

Döngüsel Kod Özellikleri:

1) üreten polinom birden fazla terim içeriyorsa, döngüsel kod tüm tekil hataları algılar. Eğer G(x)= x + 1, daha sonra kod tek hataları ve tüm tek hataları algılar;

2) ile döngüsel kod G(x)= (x + 1)G(x) tüm tek, çift ve üçlü hataları algılar;

3) polinom üreten döngüsel kod G(x) derece r = n - k sürenin tüm grup hatalarını algılar r karakterler.

Kontrol soruları

Döngüsel kodların ana özellikleri ve adı, iletilen bir mesajdaki izin verilen tüm ikili sembol kombinasyonlarının, bazı kaynak sözcüklerin döngüsel kaydırma işlemiyle elde edilebildiği gerçeğiyle ilgilidir: Genellikle, döngüsel kodun kod kombinasyonları dikkate alınır. sıfırlar ve birler dizisi biçiminde değil, bir dereceye kadar bir polinom biçiminde. Herhangi bir konumsal sayı sistemindeki herhangi bir sayı, genel biçimde şu şekilde temsil edilebilir: burada x, sayı sisteminin tabanıdır; a - verilen sayı sisteminin rakamları; n-1, n-2, ... tabanın yükseltildiği üs ve aynı zamanda basamakları kaplayan sıra sayılarıdır. İkili bir sistem için x = 2 ve ya "O" ya da "1". Örneğin, ikili kombinasyon 01001, x argümanının bir polinomu olarak yazılabilir: Bir polinom olarak bir kod kombinasyonu yazarken, 1. bitte bir x "üyesi olarak yazılır ve sıfır hiç yazılmaz. polinomlar biçimindeki kod kombinasyonları, aralarında bire bir yazışma kurmanıza ve kombinasyonlar üzerindeki eylemleri polinomlar üzerindeki eylemlere indirmenize izin verir. Böylece, ikili polinomların eklenmesi, toplama modulo 2'ye indirir. Örneğin, Çarpma şuna göre yapılır. güç fonksiyonlarının genel çarpımı kuralıdır, ancak belirli bir derece için elde edilen katsayılar modulo 2 eklenir. Örneğin, bölme polinomların normal bölümü olarak da yapılır; bu durumda çıkarma işleminin yerini toplama işlemi alır. modül 2: Yukarıda belirtildiği gibi, kodlar döngüsel olarak adlandırılır, çünkü izin verilen kombinasyonun a n ^ a l A, ..., a 2, a 1 ve d1 a n1 döngüsel kayması a n (, a n _ 2, ..., a 1, ve 0 da izin verilen bir kombinasyondur.Polinomlar biçimindeki temsiller kullanıldığında böyle bir döngüsel permütasyon, bu polinomun x ile çarpılmasının bir sonucu olarak oluşur.(x + a 0, sonra Y (x) x = an] xn + an 2 xn "1 + ... + axx 2 + a ^ x. Polinomun derecesi n-1'i geçmeyecek şekilde, x " terimi bir ile değiştirilir, bu nedenle: Örneğin, 1111110 kod kombinasyonuna sahibiz -> x + x 5 + x 3 + .xr -1-x'de bir basamak kaydıralım, şunu elde ederiz: Bu, orijinal polinomun x üzerindeki çarpımı ile aynıdır: Döngüsel kodlar oluşturma teorisi, ikili polinomların özelliklerini inceleyen yüksek cebir bölümleri Bu teoride özel bir rol, sözde indirgenemez polinomlar, yani daha düşük dereceli polinomların bir ürünü olarak temsil edilemeyen polinomlar tarafından oynanır. Ogo-üyesi sadece kendisine ve bire bölünür. Daha yüksek cebirden, x "+1 binomlarının, kalansız indirgenemez bir polinomla bölünebildiği bilinmektedir. bakınız Tablo 8.4) (9] Döngüsel bir kod oluşturma fikri, kod kombinasyonunun bilgi bölümünü temsil eden polinomun, bölünebilir olan en fazla n-1 dereceli bir polinom haline dönüştürülmesi gerektiği gerçeğine dayanmaktadır. Üreten polinom P(x) tarafından bir kalan olmadan İkincinin derecesinin basamak sayısına tekabül etmesi esastır Döngüsel kodlarda, polinomlar olarak temsil edilen tüm izin verilen kombinasyonların bir özelliği vardır: üreten tarafından kalansız bölünebilme polinom P (x) İzin verilen kod kelimesinin yapısı aşağıdakine indirgenir: 1. k uzunluğundaki kod kelimesinin bilgi kısmını O (x) polinomu şeklinde temsil ederiz. tek terimli Y ve 0 (x) xr elde edin, yani türev ¿-bit ​​kod kelimesinin r bit ile kaydırılmasıdır. 3. O (x) x "polinomunu, derecesi r'ye eşit olan üreteç polinomu P (x) ile böleriz. O (x) ile xz'nin çarpılmasının bir sonucu olarak, O ( x) r ile artar.xz O [x) ürününün z dereceli üreteç polinomuna bölündüğü zaman, 0 (x) ile aynı derecede bir C (x) bölümü elde ederiz.Bu işlemlerin sonuçları şu şekilde olabilir: şeklinde temsil edilir: (8.28) burada Ux), 0 (x) x z'yi P (x)'e bölmenin kalanıdır. C (x), 0 (x) ile aynı dereceye sahip olduğundan, C (x) aynı ¿-bit ​​kodunun bir kod sözcüğüdür. Kalanın derecesi, açıkça, üreten polinomun derecesinden daha büyük olamaz, yani en yüksek derecesi r-1'e eşittir. Sonuç olarak, kalanın en büyük rakamı r'yi geçmez.(8.28)'nin her iki tarafını P(x) ile çarparsak, sürünerek: (8.29) (çıkarma işareti, toplama modulo 2 işareti ile değiştirilir). Açıktır ki, F(x), P(x)'e kalansız bölünebilir. Polinom F (x), döngüsel kodun izin verilen modelidir. (8.29)'dan, döngüsel kodun izin verilen kod sözcüğünün iki şekilde elde edilebileceği sonucu çıkar: basit kod C(x)'in kod sözcüğünü üreten polinom P(x) ile çarparak veya kod sözcüğü 0(x) ile çarparak. basit kodun tek terimli xr ile ifade edilmesi, ürünün üreten polinom P(x) ile bölünmesiyle elde edilen kalan P(x)'in bu ürüne eklenmesi. Birinci kodlama yönteminde bilgi ve kontrol bitleri birbirinden ayrılmaz (kod ayrılmaz bir bütündür). Bu, kod çözme işleminin pratik uygulamasını zorlaştırır. İkinci yöntemle, ayrılabilir bir kod elde edilir: bilgi bitleri en yüksek konumları işgal eder, kalan n-k bitleri kontrol eder. Bu kodlama yöntemi pratikte yaygın olarak kullanılmaktadır. Örnek 3. Verilen bir 0111 kod kombinasyonu. d o = 3 olan bir döngüsel kod oluşturalım. Çözüm. İlk aşamada, gerekli d o = 3'ten yola çıkarak, l kodunun uzunluğunu ve k kontrol elemanlarının sayısını belirliyoruz.Bunun için tablo 8.6.1'i kullanacağız. Belirli bir dört bitlik N-16 kod sözcüğü için. Daha sonra, 16 bağıntısından (Tablo 8.3) d = 3 için sırasıyla n - 7'yi buluruz, k = n - m - = 7 - 4 = 3. Bu nedenle, (7.4) koduna ihtiyaç vardır. Polinom üreteçleri tablosuna göre (Tablo 8.4) k = 3 için P (x) = x 3 + x 2 + 1 belirleriz. Ayrıca: 1) 0111 mesajı için O (x) = x 2 + x + var. 1; 2) 0 (x)'i x 3 ile çarparız (r = 3 olduğundan): O (x) x 3 = (x 2 -I- x + 1) x 3 = x 5 + x 4 + x 3; 3) (E (x) x 3'ü P (x)'e böleriz: 4) elde ederiz: ^ (x) = O (x) x 3 0 R (x) = x 5 + x 4 + x 3 + 1. Bu polinom, kod kombinasyonuna karşılık gelir: Tüm bu işlemler ikili sayılar üzerinde gerçekleştirilebilir: Tablo 8.4
4) F (0,1) = O (0, l) x 3 (0, l) © R (0 1 l) = 011100000001 = 0111 001. Şimdi izin verilen kod kombinasyonunu ilk şekilde oluşturuyoruz: F ​​(x) = C ( x) P (x). Polinomları ikili sayılarla temsil eden çarpma işlemini yapalım: Alınan kod kombinasyonunda bilgileri ayırmanın ve rakamları kontrol etmenin imkansız olduğu görülmektedir. Döngüsel kodlamada hata tespiti, alınan kod sözcüğünü, kodlama sırasında kullanılan aynı üretici polinomla bölmeye indirgenir (formunun alımda bilinmesi gerekir). Alınan kod sözcüğünde herhangi bir hata yoksa (veya iletilen bu kod sözcüğü izin verilen başka bir kod sözcüğüne dönüştürülecek şekildeyse), o zaman üreten polinomla bölme, kalansız gerçekleştirilecektir. Bölme kalanla sonuçlanırsa, bu bir hata olduğunu gösterir. Örnek 4. İzin verilen bir kod sözcüğü olarak, önceki örnekte elde edilen kod sözcüğünü alın: P (x) = x 5 + x 4 + x 3 + 1 ve P (x) = x 3 + x 2 +1 veya ikili olarak E (0,1) = 0111001 formu; Р (0,1) = 1101. En anlamlı (7.) basamakta bilgilendirme kısmında bir hata oluştuğunu varsayalım (sağdan sola doğru sayıyoruz). Kabul edilen kod kombinasyonu 1111001 gibi görünüyor. Bir hata tespit işlemi gerçekleştirelim: 110'un geri kalanının varlığı bir hatayı gösterir. Döngüsel kodlar bilgi iletim sistemlerinde yaygın olarak kullanılmaktadır. Örneğin, yaygın modem protokolünde \ 7.42, kod gruplarını kodlamak için, 10001 0000 0010 0001 koduna eşdeğer olan q (X) = X 16 + X "-2 + X 5 + 1 üreten polinom kullanılır. yanı sıra daha yüksek dereceli bir polinom üreten d (X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + X2 + 1.8.6.

Bu kelimeyi resmi bir değişkenden eşleştirme x... Görüldüğü gibi bu yazışma sadece bire bir değil aynı zamanda izomorfiktir. "Kelimeler" bir alandaki harflerden oluştuğu için toplanabilir ve çarpılabilir (eleman eleman) ve sonuç aynı alanda olacaktır. Bir çift kelimenin lineer kombinasyonuna karşılık gelen polinom ve bu kelimelerin polinomlarının lineer kombinasyonuna eşittir.

Bu, sonlu bir alan üzerinde n uzunluğundaki kelimeler kümesini, alan üzerinde en fazla n-1 dereceli polinomların lineer bir uzayı olarak düşünmemizi sağlar.

cebirsel açıklama

Döngüsel olarak elde edilen kod sözcüğü sözcükten bir bit sağa kaydırılırsa, karşılık gelen polinom C 1 (x) x ile çarpılarak öncekinden elde edilir:

olduğu gerçeğinden yararlanarak,

Sırasıyla sağa ve sola kaydır J rakamlar:

Eğer m(x) alan üzerinde keyfi bir polinomdur GF(Q) ve C(x) döngünün kod sözcüğüdür ( n,k) kodu, ardından m(x)C(x)mÖNS(x n − 1) aynı zamanda bu kodun kod sözcüğüdür.

polinom oluşturma

Tanım Döngüselin üreten polinomu ( n,k) kodu C böyle sıfır olmayan bir polinom denir itibaren C, derecesi en küçük ve katsayı en yüksek derecede olan G r = 1 .

Teorem 1

Eğer C- döngüsel ( n,k) kodu ve G(x) onun üreten polinomudur, sonra derece G(x) eşittir r = n − k ve her bir kod sözcüğü benzersiz bir şekilde şu şekilde temsil edilebilir:

C(x) = m(x)G(x) ,

derece nerede m(x) küçük veya eşittir k − 1 .

Teorem 2

G(x) döngüselin üreteç polinomudur ( n,k) kodun iki terimlinin bir bölenidir x n − 1

Sonuçlar: bu nedenle, üreten bir polinom olarak, bölen herhangi bir polinomu seçebilirsiniz. x n- 1. Seçilen polinomun derecesi, kontrol sembollerinin sayısını belirleyecektir. r, bilgi sembollerinin sayısı k = n − r .

üretici matris

Polinomlar lineer olarak bağımsızdır, aksi halde m(x)G(x) = 0 sıfır olmayan m(x) ki bu imkansızdır.

Bu, kod kelimelerinin lineer kodlarda olduğu gibi aşağıdaki gibi yazılabileceği anlamına gelir:

, nerede G bir matris oluşturma, m(x) - bilgi polinom.

matris G sembolik biçimde yazılabilir:

Matrisi Kontrol Et

Döngüsel kodun her bir kod sözcüğü için doğrudur. Bu yüzden matrisi kontrol etşu şekilde yazılabilir:

kodlama

sistematik olmayan

Sistematik olmayan kodlama ile, kod kelimesi, bilgi polinomunun ürünü şeklinde üretilerek elde edilir.

C(x) = m(x)G(x) .

Polinom çarpanları kullanılarak uygulanabilir.

Sistematik

Sistematik kodlama ile kod kelimesi bir bilgi alt bloğu ve bir kontrol şeklinde oluşturulur.

Bilgi kelimesinin kod kelimenin en yüksek güçlerini oluşturmasına izin verin, o zaman

C(x) = x r m(x) + s(x),r = n − k

Sonra koşuldan, şu şekildedir

Bu denklem, sistematik kodlamanın kuralını belirler. Çok döngülü doğrusal filtreler (MLF) kullanılarak uygulanabilir.

Örnekleri

İkili (7,4,3) kod

bölen olarak x 7 - 1 üçüncü dereceden üreten polinomu seçiyoruz G(x) = x 3 + x + 1 , sonra ortaya çıkan kodun uzunluğu olacaktır n= 7, kontrol sembollerinin sayısı (oluşturan polinomun derecesi) r= 3, bilgi sembollerinin sayısı k= 4, minimum mesafe NS = 3 .

üretici matris kod:

,

ilk satırın polinom gösterimini temsil ettiği yer G(x) artan derecede katsayılar. Satırların geri kalanı, ilk satırın döngüsel kaymalarıdır.

Matrisi kontrol edin:

,

burada 0'dan başlayan i'inci sütun, bölümün geri kalanıdır. x ben polinom ile G(x), yukarıdan başlayarak artan derecelerde yazılır.

Böylece, örneğin, 3. sütun elde edilir veya vektör notasyonunda.

bunu görmek kolay GH T = 0 .

İkili (15.7.5) BCH kodu

Üreten bir polinom olarak G(x) iki bölenin çarpımını seçebilirsiniz x 15 − 1 ^

G(x) = G 1 (x)G 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Daha sonra her bir kod sözcüğü bilgi polinomunun çarpımı kullanılarak elde edilebilir. m(x) derece ile k- 1 bu şekilde:

C(x) = m(x)G(x) .

Örneğin, bilgi kelimesi polinomun karşılığına karşılık gelir. m(x) = x 6 + x 5 + x 4 + 1 , ardından kod sözcüğü C(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 veya vektör biçiminde

Ayrıca bakınız

Bağlantılar

Wikimedia Vakfı. 2010.

Diğer sözlüklerde "Döngüsel kodların" neler olduğunu görün:

kısaltılmış döngüsel kodlar- - [L.G. Sumenko. İngilizce Rusça Bilgi Teknolojileri Sözlüğü. M.: GP TsNIIS, 2003.] Genel olarak bilgi teknolojileri konuları EN kısaltılmış döngüsel kodlar ...

Veri bloklarındaki hataları düzeltmek için ikili olmayan döngüsel kodlar. Kod vektörünün elemanları bit değil, bit gruplarıdır (bloklar). Baytlarla (sekizler) çalışan Reed Solomon kodları çok yaygındır. Reed Solomon'un kodu ... Wikipedia

Golay kodları- Hata düzeltmeli mükemmel lineer blok kodları ailesi. En kullanışlısı Golay ikili kodudur. Üçlü Golay kodu da bilinmektedir. Golay kodları döngüsel kodlar olarak düşünülebilir. ... ... Teknik çevirmen kılavuzu

İletişim teknolojisindeki hataların tespiti, bilgilerin kaydedilmesi / çoğaltılması veya iletişim hatları üzerinden iletimi sırasında verilerin bütünlüğünü izlemeyi amaçlayan bir eylemdir. Sonra bilgileri geri yüklemek için hataları düzeltme (hata düzeltme) prosedürü ... ... Wikipedia

İletişim teknolojisindeki hataların tespiti, bilgilerin kaydedilmesi / çoğaltılması veya iletişim hatları üzerinden iletimi sırasında verilerin bütünlüğünü izlemeyi amaçlayan bir eylemdir. Sonra bilgileri geri yüklemek için hataları düzeltme (hata düzeltme) prosedürü ... ... Wikipedia

Bu kelimeyi resmi bir değişkenden eşleştirme x... Görüldüğü gibi bu yazışma sadece bire bir değil aynı zamanda izomorfiktir. "Kelimeler" bir alandaki harflerden oluştuğu için toplanabilir ve çarpılabilir (eleman eleman) ve sonuç aynı alanda olacaktır. Bir çift kelimenin lineer kombinasyonuna karşılık gelen polinom ve bu kelimelerin polinomlarının lineer kombinasyonuna eşittir.

Bu, sonlu bir alan üzerinde n uzunluğundaki kelimeler kümesini, alan üzerinde en fazla n-1 dereceli polinomların lineer bir uzayı olarak düşünmemizi sağlar.

cebirsel açıklama

Döngüsel olarak elde edilen kod sözcüğü sözcükten bir bit sağa kaydırılırsa, karşılık gelen polinom C 1 (x) x ile çarpılarak öncekinden elde edilir:

olduğu gerçeğinden yararlanarak,

Sırasıyla sağa ve sola kaydır J rakamlar:

Eğer m(x) alan üzerinde keyfi bir polinomdur GF(Q) ve C(x) döngünün kod sözcüğüdür ( n,k) kodu, ardından m(x)C(x)mÖNS(x n − 1) aynı zamanda bu kodun kod sözcüğüdür.

polinom oluşturma

Tanım Döngüselin üreten polinomu ( n,k) kodu C böyle sıfır olmayan bir polinom denir itibaren C, derecesi en küçük ve katsayı en yüksek derecede olan G r = 1 .

Teorem 1

Eğer C- döngüsel ( n,k) kodu ve G(x) onun üreten polinomudur, sonra derece G(x) eşittir r = n − k ve her bir kod sözcüğü benzersiz bir şekilde şu şekilde temsil edilebilir:

C(x) = m(x)G(x) ,

derece nerede m(x) küçük veya eşittir k − 1 .

Teorem 2

G(x) döngüselin üreteç polinomudur ( n,k) kodun iki terimlinin bir bölenidir x n − 1

Sonuçlar: bu nedenle, üreten bir polinom olarak, bölen herhangi bir polinomu seçebilirsiniz. x n- 1. Seçilen polinomun derecesi, kontrol sembollerinin sayısını belirleyecektir. r, bilgi sembollerinin sayısı k = n − r .

üretici matris

Polinomlar lineer olarak bağımsızdır, aksi halde m(x)G(x) = 0 sıfır olmayan m(x) ki bu imkansızdır.

Bu, kod kelimelerinin lineer kodlarda olduğu gibi aşağıdaki gibi yazılabileceği anlamına gelir:

, nerede G bir matris oluşturma, m(x) - bilgi polinom.

matris G sembolik biçimde yazılabilir:

Matrisi Kontrol Et

Döngüsel kodun her bir kod sözcüğü için doğrudur. Bu yüzden matrisi kontrol etşu şekilde yazılabilir:

kodlama

sistematik olmayan

Sistematik olmayan kodlama ile, kod kelimesi, bilgi polinomunun ürünü şeklinde üretilerek elde edilir.

C(x) = m(x)G(x) .

Polinom çarpanları kullanılarak uygulanabilir.

Sistematik

Sistematik kodlama ile kod kelimesi bir bilgi alt bloğu ve bir kontrol şeklinde oluşturulur.

Bilgi kelimesinin kod kelimenin en yüksek güçlerini oluşturmasına izin verin, o zaman

C(x) = x r m(x) + s(x),r = n − k

Sonra koşuldan, şu şekildedir

Bu denklem, sistematik kodlamanın kuralını belirler. Çok döngülü doğrusal filtreler (MLF) kullanılarak uygulanabilir.

Örnekleri

İkili (7,4,3) kod

bölen olarak x 7 - 1 üçüncü dereceden üreten polinomu seçiyoruz G(x) = x 3 + x + 1 , sonra ortaya çıkan kodun uzunluğu olacaktır n= 7, kontrol sembollerinin sayısı (oluşturan polinomun derecesi) r= 3, bilgi sembollerinin sayısı k= 4, minimum mesafe NS = 3 .

üretici matris kod:

,

ilk satırın polinom gösterimini temsil ettiği yer G(x) artan derecede katsayılar. Satırların geri kalanı, ilk satırın döngüsel kaymalarıdır.

Matrisi kontrol edin:

,

burada 0'dan başlayan i'inci sütun, bölümün geri kalanıdır. x ben polinom ile G(x), yukarıdan başlayarak artan derecelerde yazılır.

Böylece, örneğin, 3. sütun elde edilir veya vektör notasyonunda.

bunu görmek kolay GH T = 0 .

İkili (15.7.5) BCH kodu

Üreten bir polinom olarak G(x) iki bölenin çarpımını seçebilirsiniz x 15 − 1 ^

G(x) = G 1 (x)G 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Daha sonra her bir kod sözcüğü bilgi polinomunun çarpımı kullanılarak elde edilebilir. m(x) derece ile k- 1 bu şekilde:

C(x) = m(x)G(x) .

Örneğin, bilgi kelimesi polinomun karşılığına karşılık gelir. m(x) = x 6 + x 5 + x 4 + 1 , ardından kod sözcüğü C(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 veya vektör biçiminde

Ayrıca bakınız

Bağlantılar

Wikimedia Vakfı. 2010.

• Müzikte döngüsel formlar
• döngüsel sınır koşulları

Diğer sözlüklerde "Döngüsel kodların" neler olduğunu görün:

kısaltılmış döngüsel kodlar- - [L.G. Sumenko. İngilizce Rusça Bilgi Teknolojileri Sözlüğü. M.: GP TsNIIS, 2003.] Genel olarak bilgi teknolojileri konuları EN kısaltılmış döngüsel kodlar ...

Reed-Solomon kodları- veri bloklarındaki hataları düzeltmenize izin veren ikili olmayan döngüsel kodlar. Kod vektörünün elemanları bit değil, bit gruplarıdır (bloklar). Baytlarla (sekizler) çalışan Reed Solomon kodları çok yaygındır. Reed Solomon'un kodu ... Wikipedia

Golay kodları- Hata düzeltmeli mükemmel lineer blok kodları ailesi. En kullanışlısı Golay ikili kodudur. Üçlü Golay kodu da bilinmektedir. Golay kodları döngüsel kodlar olarak düşünülebilir. ... ... Teknik çevirmen kılavuzu

Hata düzeltme kodları

Kodlar düzeltilirken hata oluştu- İletişim teknolojisindeki hataların tespiti, bilgilerin kaydedilmesi / oynatılması veya iletişim hatları üzerinden iletimi sırasında verilerin bütünlüğünü izlemeyi amaçlayan bir eylem. Sonra bilgileri geri yüklemek için hataları düzeltme (hata düzeltme) prosedürü ... ... Wikipedia

Hata Düzeltme Kodları- İletişim teknolojisindeki hataların tespiti, bilgilerin kaydedilmesi / oynatılması veya iletişim hatları üzerinden iletimi sırasında verilerin bütünlüğünü izlemeyi amaçlayan bir eylem. Sonra bilgileri geri yüklemek için hataları düzeltme (hata düzeltme) prosedürü ... ... Wikipedia

döngüsel kod

Döngüsel kodlar, her bir kombinasyonun bağımsız olarak (bir blok şeklinde) kodlandığı blok sistematik kodların sayısına aittir, böylece bilgi k ve kontrol t sembolleri her zaman bulunur.

belli yerlerde giyin. Diğer kodlara kıyasla nispeten düşük bir fazlalık ile hemen hemen her türlü hatayı tespit etme ve düzeltme yeteneği ve ayrıca kodlama ve kod çözme ekipmanının devre uygulamasının basitliği bu kodları yaygın hale getirmiştir. Döngüsel kodlar teorisi, gruplar teorisine ve Galois alanı üzerindeki polinomların cebirine dayanır.

Döngüsel kod - kod kombinasyonlarının dağıtım sırasının, herhangi bir kombinasyondan komşu olana geçerken Hamming kodu mesafesinin her seferinde sabit kalacağı şekilde gerçekleştirildiği bir kod.

Döngüsel kodlar, çeşitlerinden biri olarak Hamming kodlarını içeren, ancak genellikle kod kombinasyonlarını iletirken meydana gelen hataları tespit etmek ve düzeltmek için gerekli yeteneğe sahip kodları uygulama olasılığı açısından büyük bir esneklik sağlayan bütün bir hata düzeltme kodları ailesidir. bir iletişim kanalı üzerinden Döngüsel kod, ilk k bitin birincil kodun bir kombinasyonu olduğu ve müteakip (n? K) bitlerinin kontrol olduğu sistematik blok (n, k) kodlarını ifade eder.

Döngüsel kodların oluşturulması, iletilen kod sözcüğünün, r dereceli indirgenemez polinom üretilmesiyle bölünmesi işlemine dayanır. Bölmenin geri kalanı, kontrol basamaklarını oluşturmak için kullanılır. Bu durumda, bölme işleminden önce, k-bit bilgi kodu kombinasyonunu r bit sola kaydıran bir çarpma işlemi gelir.

Daha düşük dereceli polinomların bir ürünü olarak temsil edilebilen bir polinom (polinom), indirgenebilir (belirli bir alanda), aksi takdirde - indirgenemez olarak adlandırılır. İndirgenemez polinomlar, sayı teorisindeki asal sayılara benzer bir rol oynar. İndirgenemez polinomlar P (X), ondalık veya ikili sayılar veya cebirsel bir polinom olarak yazılabilir.

Döngüsel kodlama işlemi

Döngüsel kodlama, döngüsel kodlarla ilişkili olarak bir üreteç, üreteç veya üretici polinomu (polinom) olarak adlandırılan indirgenemez bir polinom P (X) kullanımına dayanır.

Tüm kombinasyonlar için ikili kodun kombinasyonları, döngüsel kodların oluşturulması için bilgi sembolleri (k) olarak alınır. Genel durumda, verilen kod kombinasyonu Q(x), üreten polinom P(x) ile çarpılırsa, P(x) seçimine bağlı olarak belirli düzeltme özelliklerine sahip bir döngüsel kod elde ederiz. Ancak bu kodda, m kontrol karakterleri kod kombinasyonunda çok çeşitli yerlerde bulunacaktır. Bu kod sistematik değildir, bu da şematik olarak uygulanmasını zorlaştırır. Kontrol karakterleri sonuna yani bilgi karakterlerinden sonra eklenirse durum büyük ölçüde basitleştirilebilir. Bu amaçla, aşağıdaki yöntemin kullanılması tavsiye edilir:

Kodlanması gereken G (x) kod kombinasyonunu, üreten polinom P (x) ile aynı dereceye sahip olan X m tek terimlisi ile çarpıyoruz;

G (x) X m ürününü üreteç polinomu P (x m) ile böleriz:

burada Q(x) bölümün bölümüdür; R (x) kalandır.

(2.1) ifadesini P(x) ile çarparsak ve R(x)'i işareti tersine çevirmeden eşitliğin diğer kısmına aktarırsak:

Böylece eşitlik (2.2)'ye göre çevrimsel kod, yani kodlanmış mesaj F(x) iki şekilde oluşturulabilir:

Bir ikili kodun bir kod kombinasyonunun tüm kombinasyonlarla, polinom P (x) üreten tarafından çarpımı;

Belirli bir kod sözcüğü G(x)'i, üreten polinom P(x) ile aynı dereceye sahip tek bir Xm polinomu ile çarparak, G(x)Xm çarpımını aşağıdakine böldükten sonra elde edilen R(x) kalanının eklenmesiyle polinom P (NS) üretilmesi.

Mesaj kodlama

G (x) = x 3 + x 2'ye karşılık gelen 1100 kod kombinasyonunu P (x) = x 3 + x + 1 kullanarak kodlamak gerekir.

G (x)'i üçüncü dereceye sahip X m ile çarparsak, şunu elde ederiz:

(2.1)'e göre G (x) X m ürününü üreteç polinomu P (x m) ile bölerek, şunu elde ederiz:

veya ikili eşdeğerde:

Böylece, sonuç olarak, G (x) ile aynı derecede Q (x) bölümünü elde ederiz:

Q(x) = x 3 + x 2 + x> 1110

ve kalan:

Sonuç olarak, (2.2)'ye göre döngüsel bir kodla kodlanmış bir ikili kodun kombinasyonu şu şekli alacaktır:

F(x) = 1110 1011 = 1100010

Döngüsel kodun izin verilen her kod kombinasyonu, üreten polinom G(x)'in tüm olası toplamlarını temsil ettiğinden, bunlar P(x)'e kalansız bölünebilmelidir. Bu nedenle, benimsenen kod kombinasyonunun doğruluğunu kontrol etmek, onu üreten polinom tarafından bölünürken kalanın belirlenmesine indirgenir.

Kalanın alınması bir hata olduğunu gösterir. Döngüsel kodlardaki bölünmenin geri kalanı bir sendrom rolünü oynar.

Örneğin, P (x) = 1011 üreten polinom kullanılarak oluşturulan iletilen kod sözcüğü F (x) = 1100010. Girişimin etkisi altında, kod kombinasyonu F "(x) = 1000010 kombinasyonuna dönüştürüldü.

Kabul edilen kombinasyonu, üreten polinomla böleriz

Kalan R (x) = 001'in varlığı bir hatayı gösterir. Ancak, kombinasyondaki hatanın yerini doğrudan göstermez. Hatayı belirlemek için sendromun analizine dayanan birkaç yöntem vardır.

Hatanın yerini belirleyin, bunun için birimi isteğe bağlı sayıda sıfırla P (x) = 1011'e böleriz.

Numaralandırılmış öğede bir hata oluştu:

Kalıntı sayısı -2> 4-2 = 2

Yani hata ikinci elemandadır.