ციკლური კოდი

ციკლური კოდები ეხება ბლოკ სისტემური კოდების რაოდენობას, რომელშიც თითოეული კომბინაცია კოდირებულია დამოუკიდებლად (ბლოკის სახით) ისე, რომ ინფორმაციის k და საკონტროლო t სიმბოლოები ყოველთვის მოიძებნოს

ჩაცმა გარკვეულ ადგილებში. შედარებით დაბალი სიჭარბით თითქმის ნებისმიერი შეცდომის გამოვლენისა და გამოსწორების უნარმა სხვა კოდებთან შედარებით, ასევე კოდირებისა და დეკოდირების აღჭურვილობის წრიული განხორციელების სიმარტივემ გახადა ეს კოდები ფართოდ გავრცელებული. ციკლური კოდების თეორია ემყარება ჯგუფების თეორიას და პოლინომიების ალგებრას გალოის ველზე.

ციკლური კოდი - კოდი, რომელშიც კოდების კომბინაციების განაწილების წესი ხორციელდება ისე, რომ ნებისმიერი კომბინაციიდან მეზობელზე გადასვლისას ჰამინგის კოდის მანძილი ყოველ ჯერზე უცვლელი რჩება.

ციკლური კოდები არის შეცდომების შემსწორებელი კოდების მთელი ოჯახი, რომელიც მოიცავს ჰამინგის კოდებს, როგორც ერთ-ერთ სახეობას, მაგრამ ზოგადად უზრუნველყოფს უფრო დიდ მოქნილობას იმ კოდების დანერგვის შესაძლებლობის თვალსაზრისით, რომლებიც საჭიროებენ კოდის კომბინაციების გადაცემისას შეცდომების გამოვლენისა და გამოსწორების აუცილებლობას. საკომუნიკაციო არხზე. ციკლური კოდი ეხება სისტემურ ბლოკ (n, k) -კოდებს, რომლებშიც პირველი k ბიტი არის პირველადი კოდის კომბინაცია, ხოლო შემდგომი (n? K) ბიტები არის გამშვები.

ციკლური კოდების აგება ემყარება გადაცემული კოდური სიტყვის გაყოფის ოპერაციას r გრადუსიანი წარმოქმნის შეუმცირებელი მრავალწევრით. დანარჩენი გაყოფა გამოიყენება ციფრების შესამოწმებლად. ამ შემთხვევაში, გაყოფის ოპერაციას წინ უძღვის გამრავლების ოპერაცია, რომელიც k-bit ინფორმაციის კოდის კომბინაციას მარცხნივ გადააქვს r ბიტებით.

პოლინომი (პოლინომი), რომელიც შეიძლება წარმოდგენილი იყოს როგორც დაბალი ხარისხის მრავალწევრების პროდუქტი, ეწოდება შემცირებად (მოცემულ ველში), სხვაგვარად - შეუმცირებელი. შეუქცევადი პოლინომები ასრულებენ რიცხვების თეორიაში პირვანდელი რიცხვების მსგავს როლს. შეუმცირებელი მრავალწევრები P (X) შეიძლება დაიწეროს როგორც ათობითი ან ორობითი რიცხვები, ასევე ალგებრული მრავალწევრი.

ციკლური კოდირების პროცესი

ციკლური კოდირება ემყარება შეუმცირებელი მრავალწევრის P (X) გამოყენებას, რომელსაც ციკლურ კოდებთან მიმართებაში ეწოდება გენერატორი, გენერატორი ან გენერირებადი მრავალწევრიანი (მრავალწევრი).

ორობითი კოდის კომბინაციები ყველა კომბინაციისთვის აღებულია როგორც ინფორმაციის სიმბოლო k k ციკლური კოდების შესაქმნელად. ზოგად შემთხვევაში, თუ მოცემული კოდის კომბინაცია Q (x) მრავლდება მომტანი პოლინომიით P (x), ჩვენ ვიღებთ ციკლურ კოდს, რომელსაც გააჩნია გარკვეული მაკორექტირებელი თვისებები P (x) არჩევანის მიხედვით. ამასთან, ამ კოდში, გამშვები სიმბოლოები იქნება განთავსებული კოდის კომბინაციის მრავალ ადგილას. ეს კოდი არ არის სისტემატური, რაც ართულებს სქემატურად განხორციელებას. სიტუაცია შეიძლება მნიშვნელოვნად გამარტივდეს, თუ ბოლოს დაემატება საკონტროლო სიმბოლოები, ანუ ინფორმაციის სიმბოლოების შემდეგ. ამ მიზნით მიზანშეწონილია გამოიყენოთ შემდეგი მეთოდი:

ჩვენ ვამრავლებთ კოდის კომბინაციას G (x), რომლის დაშიფვრაც საჭიროა, ერთფუნქციური X m- ით, რომელსაც აქვს იგივე ხარისხი, რაც წარმოქმნის პოლინომს P (x);

ჩვენ ვყოფთ პროდუქტს G (x) X m გენერატორის მრავალწევრით P (x m):

სადაც Q (x) არის გაყოფის კოეფიციენტი; R (x) არის დარჩენილი.

გამრავლებული გამოთქმა (2.1) P (x) - ით და R (x) თანასწორობის სხვა ნაწილზე გადატანა ნიშნის საპირისპიროდ შეცვლის გარეშე, ვიღებთ:

ამრიგად, თანასწორობის მიხედვით (2.2), ციკლური კოდი, ანუ კოდირებული შეტყობინება F (x), შეიძლება ჩამოყალიბდეს ორი გზით:

ორობითი კოდის ერთი კოდის კომბინაციის გამრავლება ყველა კომბინაციით წარმოქმნილი მრავალწევრი P (x);

მოცემული კოდური სიტყვის გამრავლება ერთ პოლინომიალში X m, რომელსაც აქვს იგივე ხარისხი, რაც წარმოქმნის პოლინომს P (x), დანარჩენი R (x) დამატებით მიღებული პროდუქტის G (x) X მ გაყოფის შემდეგ წარმოქმნის პოლინომს P (NS).

შეტყობინების კოდირება

საჭიროა კოდირების კომბინაცია 1100, რომელიც შეესაბამება G (x) = x 3 + x 2 P (x) = x 3 + x + 1 გამოყენებით.

ჩვენ ვამრავლებთ G (x) X m– ს, რომელსაც აქვს მესამე ხარისხი, მივიღებთ:

G (x) X მ პროდუქტის გაყოფა გენერატორის მრავალწევრით P (x m), (2.1) მიხედვით მივიღებთ:

ან ორობითი ექვივალენტით:

ამრიგად, შედეგად, ჩვენ ვიღებთ კოეფიციენტს Q (x) იმავე ხარისხის, როგორც G (x):

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

და დანარჩენი:

შედეგად, ციკლური კოდით დაშიფრული ორობითი კოდის კომბინაცია (2.2) შესაბამისად მიიღებს ფორმას:

F (x) = 1110 1011 = 1100010

ვინაიდან ციკლური კოდის თითოეული ნებადართული კოდის კომბინაცია წარმოადგენს გენერირებული მრავალწევრის G (x) ყველა შესაძლო ჯამს, ისინი უნდა იყოფა დანარჩენის გარეშე P (x) - ზე. ამრიგად, მიღებული კოდური სიტყვის სისწორის შემოწმება მცირდება დარჩენილი ნაწილის იდენტიფიცირებით, როდესაც იგი დაყოფილია მრავალწევრიანზე.

დანარჩენის მიღება ნიშნავს შეცდომას. ციკლური კოდების დანარჩენი გაყოფა სინდრომის როლს ასრულებს.

მაგალითად, გადაცემული კოდური სიტყვა F (x) = 1100010, აგებული მომტანი მრავალწევრის P (x) = 1011 გამოყენებით. ჩარევის გავლენის ქვეშ, კოდის კომბინაცია გარდაიქმნა კომბინაციაში F "(x) = 1000010

ჩვენ მიღებულ კომბინაციას ვყოფთ წარმოქმნილ მრავალწევრად

დარჩენილი R (x) = 001 ყოფნა მიუთითებს შეცდომაზე. თუმცა, ის პირდაპირ არ მიუთითებს შეცდომის ადგილმდებარეობას კომბინაციაში. სინდრომის ანალიზზე დაფუძნებული რამდენიმე მეთოდი არსებობს შეცდომის დასადგენად.

შეცდომის ადგილმდებარეობის განსაზღვრა, ამისათვის ჩვენ ვყოფთ ერთეულს ნულოვანი რაოდენობის ნულებით P (x) = 1011.

მოხდა შეცდომა დანომრილ ელემენტში:

ნარჩენების რაოდენობა -2> 4-2 = 2

ანუ შეცდომა არის მეორე ელემენტში.

ციკლური კოდი არის წრფივი კოდი, რომელიც არის სასრული ნაკრები, რომელიც დახურულია კოდის ვექტორების ციკლური ცვლის მოქმედების მიმართ. დაე მისცეს n-განზომილებიანი ვექტორი v = ა 0 ა 1 …a n-1 სამიზნე ველიდან კოორდინატებით ფ... მისი ციკლური ცვლა არის ვექტორი v "= ა n-1 და 0 და 1 ... a n -2 .

განვიხილოთ nგანზომილებიანი არითმეტიკული სივრცე გალოის ველზე გფ(2). თითოეული ვექტორი ა 0 ა 1 …a n-1 -დან გფ(2) შეიძლება ასოცირდებოდეს ცალ-ცალკე პოლინომი ა 0 +ა 1 x+…+a n -1 x n-1 კოეფიციენტებით საწყისიდან გფ(2). ორი ვექტორის ჯამი ა 0 ა 1 …a n-1 და ბ 0 ბ 1 …ბ ნ-1 ასოცირდება შესაბამისი პოლინომების ჯამთან, ველის ელემენტების პროდუქტს ვექტორით - ამ ვექტორის შესაბამისი ელემენტის მიხედვით მრავალწევრის პროდუქტს.

განვიხილოთ რამდენიმე პოლინომი ზ(x) აღწერილი ხაზოვანი სივრციდან. ამ ქვესივრცედან ყველა მრავალწევრის ნაკრები, რომლებიც იყოფა ნარჩენების გარეშე ზ(x), ქმნის წრფივ ქვე -სივრცეს. ხაზოვანი ქვესივრცე განსაზღვრავს ზოგიერთ ხაზოვან კოდს.

წრფივი კოდი ჩამოყალიბებულია მრავალწევრების კლასით გ(ზ(x)), რამდენიმე მრავალწევრის ჯერადი ზ(x), რომელსაც ეწოდება წარმომქმნელი პოლინომი, ეწოდება მრავალწევრი.

მოდით ვაჩვენოთ, თუ როგორ არის დაკავშირებული პოლინომიური კოდები გ(ზ(x)) და ციკლური კოდები. დაე იყოს ა = ა 0 … ა-1 - ზოგიერთი კოდიანი სიტყვა და შესაბამისი კოდი მრავალწევრიანი ა(x) = ა 0 +...+a n -1 x n-1. ციკლური შეჭრა ა"შეესაბამება კოდის პოლინომიას ა"(x) = a n -1 +ა 0 x+…+a n -2 x n -1, რომელიც შეიძლება გამოიხატოს ორიგინალის საშუალებით:

ვინაიდან მრავალწევრიანი კოდი უნდა იყოფა ზ(x), შემდეგ იმისათვის, რომ ის იყოს ციკლური, პოლინომი ა"(x) უნდა იყოს გაყოფილი ზ(x). ამ თვალსაზრისით, ჩვენ შეგვიძლია ჩამოვაყალიბოთ შემდეგი თეორემა. მრავალწევრიანი კოდი არის ციკლური თუ და მხოლოდ იმ შემთხვევაში, თუ მრავალწევრიანი ზ(x) არის მრავალწევრის გამყოფი x n-1. ამ შემთხვევაში, პოლინომია ზ(x) ეწოდება ციკლური კოდის მომტანი პოლინომი.

კოდირების თეორიაში დამტკიცებულია შემდეგი თეორემა: თუ პოლინომი ზ(x) აქვს ხარისხი n–კდა არის გამყოფი x n-1, მაშინ გ(ზ(x)) არის წრფივი ციკლური ( n, კ) -კოდი.

მრავალწევრიანი x n-1 ფაქტორი x n–1 = (x–1)(x n -1 +x n-1 + ... + 1). შესაბამისად, ციკლური კოდები არსებობს ნებისმიერი n... ციკლური nბიტი კოდები უდრის მრავალწევრის გამყოფთა რაოდენობას x n-1. ციკლური კოდების შესაქმნელად შემუშავებულია მრავალწევრიანი დაშლის ცხრილი x n–1 დაუმცირებელ მრავალწევრად, ანუ იმათზე, რომლებიც იყოფა მხოლოდ ერთზე და თავისთავად.

მაგალითად, განვიხილოთ რა კოდების აგება შეიძლება მრავალწევრის საფუძველზე x 7 -1 მოედანზე გფ(2). პოლინომიის ფაქტორიზაციას შეუმცირებელ ფაქტორებად აქვს ფორმა

ვინაიდან მრავალწევრის ექვსი გამყოფი შეიძლება ჩამოყალიბდეს x 7 -1, შეუმცირებელი გამყოფების გაერთიანებით, არის ექვსი ორობითი ციკლური კოდი. ( n, კ) -კოდი განისაზღვრება, პირველ რიგში, მნიშვნელობით nდა მეორე, ღირებულება კ = n – ს, სარის გამყოფი მრავალწევრის ხარისხი x n–1 კოდის განსაზღვრა. ქვემოთ მოცემულია მრავალწევრის გამყოფი და მათი შესაბამისი მნიშვნელობები კ:

x – 1, ს=1, კ=6;

x 3 + x 2 +1, ს=3, კ=4;

x 3 + x+1, ს=3, კ=4;

(x–1)(x 3 + x 2 +1)=x 4 + x 2 + x + 1, ს=4, კ=3;

(x–1)(x 3 + x+1)=x 4 + x 3 + x 2 +1, ს=4, კ=3;

(x 3 + x 2 +1)(x 3 + x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, ს=6, კ=1.

(7, 6) კოდს აქვს მხოლოდ ერთი გამშვები სიმბოლო, ხოლო (7, 1) -კოდს -მხოლოდ ერთი საინფორმაციო. ეს არის პარიტეტი და გამეორება, შესაბამისად.

ჩვეულებრივი ხაზოვანი კოდის მსგავსად, ციკლური კოდი შეიძლება განისაზღვროს გენერატორის მატრიცით. აქედან გამომდინარე, ამოცანაა ასეთი მატრიცის პოვნა, ანუ პოვნა კხაზოვანი დამოუკიდებელი კოდის კომბინაციები, რომლებიც ქმნიან მას. ამისათვის ჩვენ გამოვიყენებთ იმ თვისებას, რომ ციკლური კოდი დახურულია ციკლური ცვლის ოპერაციასთან დაკავშირებით. გაითვალისწინეთ, რომ ციკლური გადატანა მარჯვნივ ერთი ბიტით უდრის მრავალწევრის გამრავლებას ზ(x) ჩართულია x... შემდეგ გენერირებადი მატრიცა შეიძლება აგებული იქნას გენერირებადი მრავალწევრის სტრიქონებად აღებით და კმისი ციკლური ძვრები:

მოდით ახლა განვიხილოთ, თუ როგორ, გენერატორი მრავალწევრის გამოყენებით ზ(x) = 1+x+x 3 დაშიფრულია (7, 4) კოდით. ავიღოთ, მაგალითად, 4 ბიტიანი სიტყვა (0101), რომელიც შეესაბამება პოლინომიას ვ(x) = x + x 3 ამ ორი მრავალწევრის გამრავლება.

ამ სიტყვის შესაბამისი, ფორმალური ცვლადიდან x... ჩანს, რომ ეს კორესპონდენცია არ არის მხოლოდ ერთ – ერთი, არამედ იზომორფულიც. ვინაიდან "სიტყვები" შედგება ველიდან ასოებისგან, მათი დამატება და გამრავლება შესაძლებელია (ელემენტი ელემენტზე) და შედეგი იქნება იმავე ველში. პოლინომი, რომელიც შეესაბამება წყვილი სიტყვების ხაზოვან კომბინაციას და უტოლდება ამ სიტყვების მრავალწევრების ხაზოვან კომბინაციას

ეს საშუალებას გვაძლევს განვიხილოთ n სიგრძის სიტყვების ერთობლიობა სასრულ ველზე, როგორც მრავალწევრების წრფივი სივრცე, რომლის ოდენობაც მაქსიმუმ n-1 ველზეა

ალგებრული აღწერა

თუ ციკლური გზით მიღებული კოდური სიტყვა გადადის ერთი ბიტიდან მარჯვნივ სიტყვიდან, მაშინ შესაბამისი მრავალწევრიანი გ 1 (x) მიიღება წინადან x გამრავლებით:

ისარგებლოს იმით, რომ,

მარჯვნივ და მარცხნივ გადაადგილება, შესაბამისად, მიერ ჯციფრები:

თუკი მ(x) არის თვითნებური პოლინომი ველზე გფ(ქ) და გ(xარის ციკლური კოდური სიტყვა ( n,კ) კოდი, მაშინ მ(x)გ(x)მოდ(x n − 1) ასევე არის ამ კოდის კოდირებული სიტყვა.

მრავალწევრის გენერირება

განმარტებაციკლური წარმოშობის პოლინომი ( n,კ) კოდი გეწოდება ასეთი არა ნულოვანი მრავალწევრი დან გ, რომლის ხარისხი არის ყველაზე პატარა და კოეფიციენტი უმაღლეს ხარისხზე ზ რ = 1 .

თეორემა 1

თუკი გ- ციკლური ( n,კ) კოდი და ზ(x) არის მისი წარმომქმნელი მრავალწევრი, შემდეგ ხარისხი ზ(x) უდრის რ = n − კ და თითოეული კოდი შეიძლება ცალსახად იყოს წარმოდგენილი როგორც

გ(x) = მ(x)ზ(x) ,

სადაც ხარისხი მ(x) ნაკლები ან ტოლია კ − 1 .

თეორემა 2

ზ(x) არის ციკლური წარმომქმნელი პოლინომი ( n,კ) კოდი არის ბინომიალის გამყოფი x n − 1

შედეგები:ამრიგად, როგორც წარმომქმნელი მრავალწევრი, შეგიძლიათ აირჩიოთ ნებისმიერი მრავალწევრიანი, გამყოფი x n- 1 შერჩეული მრავალწევრის ხარისხი განსაზღვრავს გამშვები სიმბოლოების რაოდენობას რ, ინფორმაციის სიმბოლოების რაოდენობა კ = n − რ .

გენერაციული მატრიცა

მრავალწევრები ხაზობრივად დამოუკიდებელია, სხვაგვარად მ(x)ზ(x) = 0 არა ნულოვანი მ(x), რაც შეუძლებელია.

ეს ნიშნავს, რომ კოდური სიტყვები შეიძლება დაიწეროს, რაც შეეხება ხაზოვან კოდებს, შემდეგნაირად:

, სად გარის მატრიცის წარმოქმნა, მ(x) - ინფორმაციაპოლინომი

Მატრიცა გშეიძლება დაიწეროს სიმბოლური ფორმით:

შეამოწმეთ მატრიცა

ციკლური კოდის თითოეული კოდური სიტყვისთვის მართალია. Ამიტომაც შეამოწმეთ მატრიცაშეიძლება დაიწეროს როგორც:

კოდირება

უსისტემო

არასისტემური კოდირებით, კოდური სიტყვა მიიღება საინფორმაციო პოლინომიის პროდუქტის სახით გენერირებით

გ(x) = მ(x)ზ(x) .

მისი განხორციელება შესაძლებელია მრავალწევრიანი გამრავლების გამოყენებით.

სისტემატური

სისტემატური კოდირებით, კოდური სიტყვა იქმნება ინფორმაციის ქვე ბლოკისა და ჩეკის სახით

დაე, ინფორმაციულმა სიტყვამ შექმნას კოდური სიტყვის უმაღლესი ძალები

გ(x) = x რ მ(x) + ს(x),რ = n − კ

შემდეგ მდგომარეობიდან გამომდინარეობს

ეს განტოლება ადგენს სისტემური კოდირების წესს. მისი განხორციელება შესაძლებელია მრავალციკლიანი წრფივი ფილტრების (MLF) გამოყენებით

მაგალითები

ორობითი (7,4,3) კოდი

როგორც გამყოფი x 7 - 1 ჩვენ ვირჩევთ მესამე ხარისხის გენერირებულ პოლინომს ზ(x) = x 3 + x + 1 , შემდეგ კოდს ექნება სიგრძე n= 7, გამშვები სიმბოლოების რაოდენობა (გენერირების მრავალწევრის ხარისხი) რ= 3, ინფორმაციის სიმბოლოების რაოდენობა კ= 4, მინიმალური მანძილი დ = 3 .

გენერაციული მატრიცაკოდი:

,

სადაც პირველი სტრიქონი წარმოადგენს მრავალწევრიან აღნიშვნას ზ(x) კოეფიციენტები აღმავალი ხარისხით. დანარჩენი ხაზები არის პირველი ხაზის ციკლური ცვლა.

შეამოწმეთ მატრიცა:

,

სადაც i- ე სვეტი, 0-დან დაწყებული, არის დანარჩენი გაყოფა x მემრავალწევრით ზ(x), დაწერილია აღმავალი ხარისხით, ზემოდან დაწყებული.

მაგალითად, მე -3 სვეტი მიიღება, ან ვექტორულ აღნიშვნაში.

ამის დანახვა ადვილია გთ თ = 0 .

ორობითი (15.7.5) BCH კოდი

როგორც წარმომქმნელი მრავალწევრი ზ(x) თქვენ შეგიძლიათ აირჩიოთ ორი გამყოფის პროდუქტი x 15 − 1 ^

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

შემდეგ თითოეული კოდური სიტყვა შეიძლება მიღებულ იქნეს ინფორმაციული მრავალწევრის პროდუქტის გამოყენებით მ(x) ხარისხით კ- 1 ამ გზით:

გ(x) = მ(x)ზ(x) .

მაგალითად, საინფორმაციო სიტყვა შეესაბამება პოლინომიას მ(x) = x 6 + x 5 + x 4 + 1 , შემდეგ კოდიანი სიტყვა გ(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 , ან ვექტორული ფორმით

იხილეთ ასევე

ბმულები

ვიკიმედიის ფონდი. 2010 წ.

• ციკლური ფორმები მუსიკაში
• ციკლური სასაზღვრო პირობები

ნახეთ რა არის "ციკლური კოდები" სხვა ლექსიკონებში:

შემცირებული ციკლური კოდები- - [ლ.გ. სუმენკო. ინფორმაციული ტექნოლოგიების ინგლისური რუსული ლექსიკონი. M.: GP TsNIIS, 2003.] თემები საინფორმაციო ტექნოლოგიები ზოგადად EN შემოკლებული ციკლური კოდები ...

რიდ-სოლომონის კოდები- არაბინარული ციკლური კოდები მონაცემთა ბლოკებში შეცდომების გამოსასწორებლად. კოდის ვექტორის ელემენტები არ არის ბიტები, არამედ ბიტების ჯგუფები (ბლოკები). რიდ სოლომონის კოდები, რომლებიც მუშაობს ბაიტებთან (ოქტეტებთან), ძალიან გავრცელებულია. რიდ სოლომონის კოდია ... ვიკიპედია

გოლეს კოდები- სრულყოფილი ხაზოვანი ბლოკის კოდების ოჯახი შეცდომის კორექციით. ყველაზე სასარგებლოა გოლეის ორობითი კოდი. ასევე ცნობილია გოლას სამი კოდი. Golay კოდები შეიძლება ჩაითვალოს როგორც ციკლური კოდები. ... ... ტექნიკური თარჯიმნის სახელმძღვანელო

შეცდომის კორექტირების კოდები

მოხდა კოდების გასწორება- საკომუნიკაციო ტექნოლოგიაში შეცდომების გამოვლენა, ქმედება, რომელიც მიზნად ისახავს მონაცემთა მთლიანობის მონიტორინგს ინფორმაციის ჩაწერის / დაკვრის დროს ან მისი გადაცემისას საკომუნიკაციო ხაზებზე. შეცდომების გასწორება (შეცდომების გამოსწორება) ინფორმაციის აღდგენის პროცედურა ... ... ვიკიპედია

კოდების გასწორების შეცდომა- საკომუნიკაციო ტექნოლოგიაში შეცდომების გამოვლენა, ქმედება, რომელიც მიზნად ისახავს მონაცემთა მთლიანობის მონიტორინგს ინფორმაციის ჩაწერის / დაკვრის დროს ან მისი გადაცემისას საკომუნიკაციო ხაზებზე. შეცდომების გასწორება (შეცდომების გამოსწორება) ინფორმაციის აღდგენის პროცედურა ... ... ვიკიპედია

ბელარუსიის სახელმწიფო საინფორმაციო და რადიოელექტრონული უნივერსიტეტი

რესურსების დეპარტამენტი

რეზიუმე თემაზე:

”ციკლური კოდები. BChH კოდები "

მინსკი, 2009 წ

ციკლური კოდები

ციკლური კოდი არის წრფივი ბლოკი (n, k) -კოდი, რომელიც ხასიათდება ციკლური თვისებით, ე.ი. ნებისმიერი ნებადართული კოდური სიტყვის მარცხენა გადანაცვლება ერთი და იმავე კოდის კუთვნილ დასაშვებ კოდურ სიტყვას და რომელშიც კოდირებული სიტყვების ნაკრები წარმოდგენილია ხარისხის პოლინომების ნაკრებით (n-1) და ნაკლები, იყოფა ზოგიერთ პოლინომზე g ( x) ხარისხის r = nk რომელიც არის xin +1 ბინომიუმის ფაქტორი.

პოლინომს g (x) ეწოდება გენერირება.

როგორც განსაზღვრებიდან გამომდინარეობს, ციკლური კოდით კოდირებული სიტყვები წარმოდგენილია მრავალწევრების სახით

სადაც n არის კოდის სიგრძე; არის კოეფიციენტები ველიდან GF (q).

თუ კოდი აგებულია GF (2) ველზე, მაშინ კოეფიციენტები იღებენ მნიშვნელობებს 0 ან 1 და კოდს ეწოდება ორობითი.
მაგალითი.თუ ციკლური კოდური სიტყვა

შემდეგ შესაბამისი პოლინომი

მაგალითად, თუ კოდი აგებულია ველზე GF (q) = GF (2 3), რომელიც არის GF (2) მოდულის გაფართოება დაუმცირებელი მრავალწევრი f (z) = z 3 + z + 1 და ელემენტები ამ ველს აქვს ფორმა წარმოდგენილი ცხრილში 1,

შემდეგ კოეფიციენტები

მიიღეთ ამ სფეროს ელემენტების მნიშვნელობები და, შესაბამისად, ისინი თავად არიან ნაჩვენები, როგორც შემდეგი ფორმის მრავალწევრები
სადაც m არის მრავალწევრის ხარისხი, რომელიც გამოიყენება GF ველის გაფართოების მისაღებად (2); a - კოეფიციენტები, რომლებიც იღებენ GF (2) ელემენტების მნიშვნელობას, ე.ი. 0 და 1. ასეთ კოდს ეწოდება qth.

ციკლური კოდის სიგრძეს ეწოდება პრიმიტიული და თავად კოდს ეწოდება პრიმიტიული, თუ მისი სიგრძე არის n = q m -1 GF (q).

თუ კოდის სიგრძე ნაკლებია პრიმიტიული კოდის სიგრძეზე, მაშინ კოდს ეწოდება მოწყვეტილი ან არა პრიმიტიული.

როგორც განსაზღვრებიდან გამომდინარეობს, ციკლური კოდური სიტყვების საერთო თვისებაა მათი დაყოფა დანარჩენი ნაწილის გარეშე პოლინომზე g (x), რომელსაც გენერირება ეწოდება.

ბინომინალის x n +1 მრავალწევრიანზე g (x) გაყოფის შედეგი არის გამშვები მრავალწევრიანი h (x).

ციკლური კოდების გაშიფვრისას გამოიყენება შეცდომის მრავალწევრი e (x) და სინდრომული მრავალწევრი S (x).

ხარისხის შეცდომის პოლინომია მაქსიმუმ (n-1) განისაზღვრება გამოთქმიდან

სად არის პოლინომი, რომელიც წარმოადგენს შესაბამისად მიღებულს (შეცდომით) და გადაცემულ კოდირებულ სიტყვებს.

E (x) - ში ნულოვანი კოეფიციენტები იკავებენ პოზიციებს, რომლებიც შეესაბამება შეცდომებს.

მაგალითი.

ციკლური კოდის დეკოდირებისას გამოყენებული სინდრომული პოლინომი განისაზღვრება, როგორც დარჩენილი კოდირებული სიტყვის გამყოფი შემქმნელი მრავალწევრით, ე.ი.

ან

შესაბამისად, სინდრომული პოლინომი პირდაპირ დამოკიდებულია შეცდომის პოლინომზე e (x). ეს პოზიცია გამოიყენება დეკოდირების პროცესში გამოყენებული სინდრომების ცხრილის შესაქმნელად. ეს ცხრილი შეიცავს შეცდომების მრავალწევრების ჩამონათვალს და გამოთქმიდან განსაზღვრული შესაბამისი სინდრომების ჩამონათვალს

(იხ. ცხრილი 2).

დეკოდირების პროცესში სინდრომი გამოითვლება მიღებული კოდიდან, შემდეგ ცხრილში გვხვდება შესაბამისი მრავალწევრიანი e (x), რომლის ჯამი მიღებული კოდირებული სიტყვით იძლევა გასწორებულ კოდ სიტყვას, ე.ი.

ჩამოთვლილი მრავალწევრები შეიძლება დაემატოს, გამრავლდეს და დაიყოს ალგებრის ცნობილი წესების გამოყენებით, მაგრამ შედეგის შემცირებით mod 2 და შემდეგ mod xn +1, თუ შედეგის ხარისხი აღემატება ხარისხს (n-1) რა

დავუშვათ, რომ კოდის სიგრძეა n = 7, მაშინ შედეგი მოცემულია mod x 7 +1.

მრავალწევრების გაყოფის შედეგად ციკლური კოდების აგებისა და გაშიფვრისას, ჩვეულებრივ, საჭიროა არა კოეფიციენტი, არამედ დანარჩენი გაყოფა.
აქედან გამომდინარე, რეკომენდებულია გაყოფის უფრო მარტივი მეთოდი, რომელიც გამოიყენება არა პოლინომიების, არამედ მხოლოდ მისი კოეფიციენტების გამოყენებით (ვარიანტი 2 მაგალითში).

მაგალითი.

კოდების მატრიცული მინიჭება

ციკლური კოდი შეიძლება განისაზღვროს გენერატორის და პარიტეტული მატრიცებით. მათი კონსტრუქციისთვის საკმარისია იცოდეთ გენერატორი g (x) და გამშვები პოლინომელი h (x). არასისტემატური ციკლური კოდისთვის მატრიცები აგებულია გენერატორის ციკლური ცვლის გზით და ამოწმებენ მრავალწევრებს, ე.ი. მათი x გამრავლებით

და

მატრიცის H (n, k) აგებისას, პოლინომიის h (x) წამყვანი კოეფიციენტი მდებარეობს მარჯვნივ.

მაგალითი.ციკლური (7,4) კოდისთვის გენერირებული მრავალწევრით g (x) = x 3 + x + 1, მატრიცებს G (n, k) და H (n, k) აქვთ ფორმა:

სად

სისტემური ციკლური კოდისთვის მატრიცა G (n, k) განისაზღვრება გამოთქმიდან

სადაც მე k არის იდენტობის მატრიცა; R k, r არის მართკუთხა მატრიცა. მატრიცის R k, r რიგები განისაზღვრება გამონათქვამებიდან ან სადაც i (x) არის მატრიცის I k რიგის i- ე რიგის მნიშვნელობა; i არის მატრიცის რიგის ნომერი R k, r.

მაგალითი.მატრიცა G (n, k) (7,4) კოდისთვის, რომელიც დაფუძნებულია გენერირებულ პოლინომზე g (x) = x 3 + x + 1 აგებულია შემდეგი თანმიმდევრობით

ან

განსაზღვრეთ R 4.3 გამოყენებით

რადგან

ანალოგიურად, განისაზღვრება