Elias Omega Kodlaşdırma

Giriş

Elias kodu, böyük ədədlərin kiçik ədədlərə nisbətən daha az ehtimalla əldə edildiyi və kodlanacaq ədədlərin kardinallığı haqqında əvvəlcədən məlumat olmadıqda, müsbət tam ədədləri səmərəli şəkildə kodlamaq üçün istifadə edilə bilər. Lakin, praktik səbəblərə görə, bu müsabiqədə giriş ədədlərinin ölçüsünə məhdudiyyət qoyuruq və giriş ədədini 1-dən böyük olmaqla məhdudlaşdırırıq.

Elias kodunun üç variantı mövcuddur: Elias gamma, Elias delta və Elias omega kodlama üsulları. Bu problem Elias gamma və Elias omega üsullarını təqdim edir və Elias omega kodunu tətbiq etməyi tələb edir. Aşağıda problemin arxa planı, tərifi və izahı verilmişdir.

Arxa Plan

Tutaq ki, Alice müsbət tam ədəd n-i Bob-a ikili kanal vasitəsilə ötürmək istəyir və β n n-in ikili təsvirini ifadə edir. Əgər Bob əvvəldən |β(n)| (n-in ikili təsviri üçün tələb olunan bitlərin sayı) bilirsə, onda Alice ötürmə üçün β(n) istifadə etməlidir. Digər tərəfdən, əgər Bob bu məlumatı bilmirsə, onda Alice əvvəlcə |β(n)| göndərə bilər, səmərəli və fərqləndirilə bilən kodlama istifadə edərək, sonra isə faktiki beta kodunu göndərə bilər F_1= β (n). Nəticədə iki sahəli kod < F_1, F_2 > alınır.

Elias kodu və onun variantları bu iki məlumat parçasını (F_1 və F_2) kodlama üsulunda fərqlənir. Variantlar arasındakı əsas fərq F_1-in təsvirindədir. Bu, F_1-in təsvirində dəyişikliklər tələb edə bilər. Bundan əlavə, bəzi variantlar F_1-in təsvirinə təkrarlama və ya rekursiya tətbiq edir. Aşağıda göstərilən xüsusi variantdan istifadə edirik.

Tərif

Rəsmi olaraq, Elias gamma kodlamasında müsbət tam ədəd n iki birləşdirilmiş bit sahəsi istifadə edilərək kodlanır. Birinci sahə, prefiks, [log_2n] bit 0 ([x] x-in döşəmə dəyəridir) ehtiva edir. İkinci sahə, postfiks, n-in faktiki ikili təsvirini [log2 n]+1 bit istifadə edərək ehtiva edir. Məsələn, onluq 9 ədədinin ikili təsviri 1001-dir. Elias kodlamasında 9 0001001 kimi kodlanır. İlk üç sıfır 9-un ikili təsviri üçün dörd bit tələb olunduğunu göstərir. Növbəti dörd bit 9-un ikili təsvirini ehtiva edir. Elias delta kodu gamma kodunun prefiksinə ([log_2n]) gamma kodunu tətbiq edir və Elias omega kodu [log_2n]-in Elias gamma təsvirinin prefiksinə rekursiya tətbiq edir.

İzah (ətraflı nümunə)

Elias omega kodunu daha da izah etmək üçün 536870907 ədədini nəzərdən keçirin. Bu ədədin ikili təsviri 1 1111 1111 1111 1111 1111 1111 1011-dir və bu 29 bit tələb edir. Beləliklə, birinci addımda aşağıdakı kimi kodlanır:

< F_1, F_2 > = < 0000 0000 0000 0000 0000 0000 0000, 1 1111 1111 1111 1111 1111 1111 1011>

burada boşluqlar, nöqtələr, vergüllər və mötərizələr oxunaqlılığı artırmaq üçün əlavə edilmişdir.

Vurğulamaq üçün, bu müsabiqədə rekursiya birinci sahədə bir 0 olan rekursiv mərhələ ilə dayandırılır.

Bütün addımlar tərəfindən yaradılan bitlərə baxaraq və β(n)-i n-in ikili təsviri olaraq göstərərək, aşağıdakıları əldə edirik:

a. <28 0-lar, β(536870907)> = < 0000 0000 0000 0000 0000 0000 0000, 1 1111 1111 1111 1111 1111 1111 1011>

b. < <4 0-lar, β(28)>, β(536870907) > = < <0000, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>

c. «<2 0-lar, β(4)>, β(28)> , β(536870907) > = < «00, 100>, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>

d. «<, β(4)>, β(28)>, β(536870907 ) > = < «<0, 10>, 100>, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>

Bütün boşluqları, nöqtələri, vergülləri və mötərizələri çıxardıqda, 536870907-nin Elias omega kodu: 0101001110011111111111111111111111111011-dir. Bu kod fərqləndirilə biləndir (unikal şəkildə dekodlana bilər). Bu, unikal şəkildə dekodlana bilər və 536870907 ədədini geri qaytarar.

Problem bəyanatı

2 – 2×10^9 aralığında bəzi müsbət tam ədədlər verildikdə, bu ədədlər üçün Elias omega kodlarını istehsal edən bir proqram yazmalısınız.