Implementasi perangkat lunak perkalian di bidang Galois

Saya ingin membuat transmisi informasi yang lebih andal melalui saluran radio. Ini bukan semacam proyek industri, atau sesuatu yang serius. Ini lebih untuk hobi dan pengembangan diri. Trauma masa kanak-kanak terpengaruh - kurangnya mobil yang dikendalikan radio yang biasanya berfungsi. Sejak itu, saya selalu ingin dapat dengan mudah dan alami mengontrol apa pun di radio ...

Jadi, saya ngelantur. Di masa kanak-kanak dan remaja, untuk pengkodean koreksi kesalahan, seseorang dapat menerapkan pemeriksaan paritas dengan metode matriks, tetapi sekarang ini tidak serius. Setelah melihat-lihat Internet, saya memutuskan untuk berhenti membuat kode menggunakan metode Reed-Solomon. Algoritme ini tidak sepenuhnya baru, ini digunakan di CD pertama, tetapi pada saat yang sama, sejauh yang saya tahu, itu tidak kehilangan relevansinya saat ini. Dalam artikel tentang kode Reed-Solomon itu sendiri, saya tidak akan banyak memperluas - ini telah dilakukan untuk saya di Habré berkali-kali dan oleh banyak orang. Di sini saya ingin menjelaskan implementasi dari algoritma perkalian di GF [256]. Namun demikian, agar tidak memaksa pembaca untuk melompat ke tautan, saya akan menjelaskan secara singkat mengapa Anda harus berurusan

dengan bidang Galois sama sekali .

Reed-Solomon Redundant Coding adalah tentang matriks. Kami menggunakan matriks untuk encoding dan decoding. Dalam proses ini, ada operasi perkalian matriks dan operasi mencari matriks invers - pembagian. Pembagian di sini tidak membutuhkan perkiraan bilangan bulat, tetapi yang paling nyata, tepat. Dan pembagian yang tepat untuk komputer adalah tugas yang tidak terpecahkan: membagi satu dengan tiga adalah bilangan bulat nol dan jumlah tak terbatas tiga kali lipat setelah titik desimal, tetapi 640 kilobyte sudah cukup untuk semua orang.

Galois hidup di awal abad ke-19, dia hidup sangat sedikit (21 tahun, secara umum tentang kepribadiannya ceritanya menarik, tapi sekarang bukan tentang itu). Karyanya sangat berguna dalam pengkodean digital. Bidang Galois berhingga adalah sekumpulan bilangan dari nol sampai n. Inti dan minat bidang ini adalah bahwa untuk elemen himpunan ini, Anda dapat menentukan operasi penjumlahan-perkalian-pengurangan-pembagian sedemikian rupa sehingga hasil operasi akan berada di bidang ini sendiri. Misalnya, mari kita set (bidang):

$$

$$[0,1,2,3,4,5,6,7]$$

2 + 2 = 4 di bidang ini, serta di bidang bilangan real biasa kita. Tapi 5 + 6 bukan 11, seperti yang biasa kita lakukan, tapi 5 + 6 = 3, dan ini bagus! 3 termasuk dalam bidang ini (secara umum, penambahan dan pengurangan untuk bidang khusus ini hanya XOR bitwise). Untuk perkalian dan pembagian, aturannya juga dipenuhi: hasil dari perkalian atau pembagian dua angka dari lapangan (himpunan ... Selanjutnya saya hanya akan berbicara "bidang") akan berada di bidang ini.

, . « » , ( « », « »). , , 256, ( ) 8, . GF[256], GF Galois Field.

. , , , , , « » ( stm32 ) - .

Sedikit tentang aritmatika. Penjumlahan dan pengurangan, seperti yang disebutkan sebelumnya, adalah operasi yang sama di bidang Galois (ini persis kasus untuk bidang basis 2), dan ini diimplementasikan sebagai XOR bitwise.

$$

$$A+B = A \operatorname{xor} B$$

$$

$$A-B = A \operatorname{xor} B$$

Mengerikan. Tetapi ketika sampai pada perkalian dan pembagian, seseorang membaca sesuatu yang bagi seseorang dengan hubungan yang tegang dengan matematika (ya, ini tentang saya) tidak sejelas hari di bulan.

Saat mengalikan, setiap operan direpresentasikan sebagai polinomial. Itu terjadi sebagai berikut: representasi biner dari nomor tersebut diambil, dan jumlahnya ditulis, di mana pangkat x adalah nomor dari digit biner, dan koefisiennya adalah nilai digit.

Contoh:

$$

$$5=101_2=1\cdot x^2+0\cdot x^1+1\cdot x^0=x^2+1$$

Selanjutnya, polinomial dikalikan sesuai dengan aturan perkalian polinomial, yaitu, setiap suku dalam kurung siku pertama dikalikan dengan setiap suku pada kurung kedua, tetapi tidak hanya seperti itu, tetapi dengan mempertimbangkan fakta bahwa koefisien tidak boleh lebih dari satu.

$$

$$x^2+x^2=0$$

$$

$$x^2+x^2+x^2=x^2$$

$$

$$x^2+x^2+x^2+x^2=0$$

Artinya, koefisien ditambahkan modulo 2. Contoh perkalian dalam GF [8]:

$$

$$6\cdot 3 = 110_2\cdot 11_2= (1\cdot x^2+1\cdot x^1+0\cdot x^0)\cdot (1\cdot x^1+1\cdot x^0)=$$

$$

$$=(x^2+x)(x+1)=x^2\cdot x+x^2\cdot 1+x\cdot x+x\cdot 1=$$

$$

$$=x^3+x^2+x^2+x$$

Kemudian kami "menambahkan" (dalam tanda kutip - karena modulo 2) istilah yang mirip, dan kami mendapatkan $$$x^3+x$, yang kami ubah ke angka biasa $$$1010_2=10$...

GF[8], 10 : « ? 10 [0,1,2,3,4,5,6,7]». . . ( ), . , , «» . ? ? ( , , , ). , . GF[8] : 11 13, 1011 1101 $$$x^3+x+1$ $$$x^3+x^2+1$

, 6 3 GF[8] . $$$x^3+x$ . $$$x^3+x+1$. , , - «», . . , $$$x^3$ ( $$$x^3$). 1. ( $$$x^3+x+1$). , ( GF[8] ) $$$(x^3+x) +(x^3+x+1)$. 2, , 1. , ( ) ( ). , , ( – ), 1.

. $$$6 \cdot 3 = 1$ GF[8] c 11.

. - 256256 ( 88, ), . , . — , . , , ( 0). , GF[8] 2,

$$$2^0=1$      $$$2^7=1$

$$$2^1=2$      $$$2^8=2$

$$$2^2=4$      $$$2^9=4$

$$$2^3=3$      $$$2^{10}=3$

$$$2^4=6$      $$$2^{11}=6$

$$$2^5=7$      $$$2^{12}=7$

$$$2^6=5$      $$$2^{13}=5$

, , 1 7 2 . , $$$2^7=2^0$ $$$2^8=2^1$, $$$2^9=2^2$dan seterusnya. Ini berarti bahwa 2 pangkat apa pun dapat direpresentasikan sebagai dua pangkat dari nol hingga 6 menggunakan operasi untuk memperoleh sisa pembagian dengan 7 dalam kasus pangkat positif dan rumus sederhana$$$2^{-x}=2^{(7-(x\: mod\:7))}$jika eksponennya adalah angka negatif

Sebenarnya, jika kita mengingat sifat mengalikan derajat, maka mengalikan angka sangat disederhanakan. Dan untuk mengalikan 6 dengan 3, sekarang kita lihat berapa derajat dua sama dengan 6 dan berapa derajat dua sama dengan 3, tambahkan pangkat dan lihat hasilnya - dua sampai batas tertentu, yang dapat direpresentasikan sebagai 2 pangkat dari 0 sampai 6 contoh:

$$

$$6\cdot 3=2^4\cdot 2^3=2^{(4+3)} = 2^7 = 2^0 = 1$$

Dengan pembagian, semuanya menjadi sangat jelas juga:

$$

$$3/6=2^3/2^4=2^{(3-4)} = 2^{-1} = 2^{(7-(1\: mod\:7))} = 2^6 = 5$$

Dan sepertinya ini dia! kebahagiaan programmer adalah penerapan aritmatika di bidang Galois - beberapa baris kode, tidak perlu repot dengan polinomial ... Ya, dan kinerja kode seperti itu akan tinggi, tetapi kemudian saya mengalami satu masalah lagi: Tabel pangkat dua di bidang GF [8] dengan menghasilkan polinomial 11 ditemukan dengan mudah. Bahkan sumber daya ini. Tapi saya tidak googling tabel derajat untuk GF [256], jadi saya memutuskan untuk mengkompilasinya sendiri, C # akan membantu saya. Saya harus menerapkan algoritma perkalian sesuai dengan aturan polinomial.

Berikut ini adalah fungsi perkalian untuk GF [2 ^ n] dengan polinomial sembarang. Pembatasan - Saya menggunakan aritmatika 32-bit, jadi n harus kurang dari 16. Juga di sini ditambahkan fungsi untuk mencari jumlah bit paling signifikan dari suatu angka

private uint GetLeadBitNum(UInt32 Val) {
    int BitNum = 31;
    uint CmpVal = 1u << BitNum;
    while (Val < CmpVal) {
        CmpVal >>= 1;
        BitNum--;
    }
    return (uint)BitNum;
}
private uint Galois_b2_ext_mult(uint m1, uint m2, uint Poly) {
    if (0 == m1 || 0 == m2) { return 0; }
    uint m1_tmp = m1;
    uint m2_tmp;
    uint m1_bit_num = 0;
    
    //  ,      2   .
    //    (         ( )),    ,
    //  ,       - ,      ,       
    //( -      2)
    uint PolyMultRez = 0;

    while (m1_tmp != 0) {
        uint bit_m1 = (m1_tmp & 1u) == 0u ? 0u : 1u;
        m1_tmp = m1_tmp >> 1;
        m2_tmp = m2;
        uint m2_bit_num;
        m2_bit_num = 0;
        while (m2_tmp != 0) {
            uint bit_m2 = (m2_tmp & 1u) == 0u ? 0u : 1u;
            m2_tmp = m2_tmp >> 1;
            if ((bit_m1 != 0) && (bit_m2 != 0)) {
                int BitNum = (int)(m2_bit_num + m1_bit_num);
                PolyMultRez ^= 1u << BitNum;
            }
            m2_bit_num = m2_bit_num + 1;
        }
        m1_bit_num = m1_bit_num + 1;
    }

    //     PolyMultRez.         .
    //   :    ,     . 
    //  -  
    // ,   ,         
    //    ,        
    uint TmpDivisor_lead_bit_n;
    uint TmpQuotient;
    uint TmpDivisor = Poly;
    uint TmpDividend = PolyMultRez;
    uint TmpDividend_LeadBitNum;
    uint TmpMult_bitNum;
    uint TmpMult_rez;

    TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
    TmpDivisor_lead_bit_n = GetLeadBitNum(TmpDivisor);

    while (TmpDividend_LeadBitNum >= TmpDivisor_lead_bit_n) {

        TmpQuotient = (TmpDividend_LeadBitNum - TmpDivisor_lead_bit_n);

        TmpMult_bitNum = 0;
        TmpMult_rez = 0;
        while (TmpDivisor != 0) {
            uint bit_TmpMult = (TmpDivisor & 1u) == 0u ? 0u : 1u;
            TmpDivisor >>= 1;
            TmpMult_rez ^= bit_TmpMult << (int)(TmpQuotient + TmpMult_bitNum);
            TmpMult_bitNum = TmpMult_bitNum + 1;
        }
        TmpDividend = TmpDividend ^ TmpMult_rez;
        TmpDivisor = Poly;
        TmpDividend_LeadBitNum = GetLeadBitNum(TmpDividend);
    }            
    //           .
    return TmpDividend;
}

Sekarang, dengan menggunakan fungsi di atas, Anda dapat membuat tabel pangkat dua untuk GF I need [256] dan menulis modul aritmatika Galois untuk stm32 menggunakan dua tabel masing-masing 256 - satu untuk langsung, yang kedua untuk mengubah bilangan kembali menjadi pangkatnya. Saya bahkan belum mulai menerapkan pengkodean Reed-Solomon, tetapi ketika sudah siap, saya rasa saya akan membagikannya di sini. Semoga lebih singkat.