🙏 🤕 🤸🏿 تنفيذ برمجيات الضرب في حقول جالوا 👊🏾 🦊 🦆

أردت بطريقة أو بأخرى إجراء نقل موثوق للمعلومات عبر قناة الراديو. هذا ليس نوعًا من المشاريع الصناعية ، أو أي شيء آخر خطير. إنها أكثر للهوايات وتطوير الذات. متأثر بصدمات الطفولة - عدم وجود سيارة تعمل بالتحكم اللاسلكي. منذ ذلك الحين ، أردت دائمًا أن أكون قادرًا على التحكم بسهولة وبشكل طبيعي في أي شيء على الراديو ...

وهكذا ، أستطرد. في مرحلة الطفولة والمراهقة ، من أجل ترميز تصحيح الأخطاء ، يمكن للمرء تطبيق فحص التكافؤ بطريقة المصفوفة ، لكن هذا ليس خطيرًا الآن. بعد أن نظرت عبر الإنترنت ، قررت التوقف عن الترميز باستخدام طريقة Reed-Solomon. الخوارزمية ليست جديدة تمامًا ، فقد تم استخدامها في الأقراص المضغوطة الأولى ، لكنها في الوقت نفسه ، على حد علمي ، لم تفقد أهميتها في الوقت الحالي. في هذا المقال حول رموز ريد-سولومون نفسها ، لن أتوسع كثيرًا - لقد تم ذلك من أجلي في حبري عدة مرات ومن قبل العديد من الأشخاص. هنا أريد أن أصف تنفيذ خوارزمية الضرب في GF [256]. ومع ذلك ، من أجل عدم إجبار القارئ على القفز على الروابط ، سوف أصف بإيجاز سبب

وجوب التعامل مع حقول جالوا على الإطلاق .

ترميز ريد-سولومون عن المصفوفات. نستخدم المصفوفات للترميز وفك التشفير. في هذه العمليات ، توجد عمليات ضرب المصفوفات وعمليات إيجاد المصفوفات المعكوسة - القسمة. القسمة هنا لا تتطلب عددًا صحيحًا تقريبيًا ، ولكنها تتطلب الأكثر واقعية ودقة. والتقسيم الدقيق لجهاز الكمبيوتر هو مهمة غير قابلة للحل: قسمة واحد على ثلاثة هي صفر أعداد صحيحة وعدد لا حصر له من ثلاثة أضعاف بعد الفاصلة العشرية ، ولكن 640 كيلو بايت ستكون كافية للجميع.

عاش جالوا في بداية القرن التاسع عشر ، عاش قليلاً جدًا (21 عامًا ، بشكل عام حول شخصيته ، القصة مثيرة للاهتمام ، لكنها الآن لا تتعلق بذلك). كان عمله مفيدًا جدًا في الترميز الرقمي. حقل جالوا المحدود هو مجموعة من الأعداد من صفر إلى ن. جوهر هذه الحقول واهتمامها هو أنه بالنسبة لعناصر هذه المجموعة ، يمكنك تحديد عمليات الجمع-الضرب-الطرح-القسمة بحيث تكون نتيجة العملية في هذا المجال نفسه. على سبيل المثال ، لنأخذ مجموعة (حقل):

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

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

2 + 2 = 4 في هذا المجال ، وكذلك في مجال الأعداد الحقيقية المعتادة. لكن 5 + 6 ليست 11 كما تعودنا ، لكن 5 + 6 = 3 ، وهذا شيء عظيم! تم تضمين 3 في هذا الحقل (بشكل عام ، الجمع والطرح لهذا الحقل المعين هو فقط XOR بت). بالنسبة للضرب والقسمة ، يتم أيضًا استيفاء القاعدة: النتيجة من ضرب أو قسمة أي رقمين من الحقل (مجموعة ... علاوة على ذلك سأتحدث فقط "الحقل") ستكون في هذا المجال.

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

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

قليلا عن الحساب. الجمع والطرح ، كما ذكرنا سابقًا ، هما نفس العملية في حقول Galois (هذا هو الحال تمامًا لحقول الأساس 2) ، ويتم تنفيذه على أنه XOR.

A + B = A xor B

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

A - B = A xor B

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

فقط مروع. ولكن عندما يتعلق الأمر بالضرب والقسمة ، فإن المرء يقرأ شيئًا لا يبدو واضحًا بالنسبة لشخص لديه علاقات متوترة مع الرياضيات (نعم ، هذا عني) مثل يوم على القمر.

عند الضرب ، يتم تمثيل كل معامل على أنه كثير الحدود. يحدث على النحو التالي: يتم أخذ التمثيل الثنائي للرقم ، ويتم كتابة المجموع ، حيث تكون قوة x هي رقم الرقم الثنائي ، ومعامله هو قيمة الرقم.

مثال:

5 = 101_{2} = 1 \cdot x^{2} + 0 \cdot x^{1} + 1 \cdot x^{0} = x^{2} + 1

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

علاوة على ذلك ، يتم ضرب كثيرات الحدود وفقًا لقواعد ضرب كثيرات الحدود ، أي أن كل مصطلح في القوس الأول يتم ضربه في كل مصطلح في الفئة الثانية ، ولكن ليس هكذا فقط ، ولكن مع الأخذ في الاعتبار حقيقة أن المعامل لا يمكن أن يكون أكثر من واحد.

x^{2} + x^{2} = 0

$x^2+x^2=0$

x^{2} + x^{2} + x^{2} = x^{2}

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

x^{2} + x^{2} + x^{2} + x^{2} = 0

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

أي ، تمت إضافة المعاملات modulo 2. مثال على الضرب في 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}) =

$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^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

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

ثم "نضيف" (في علامات الاقتباس - لأن المقياس 2) مصطلحات متشابهة ، ونحصل عليها

x^{3} + x

$x^3+x$ ، والذي نحوله إلى الرقم المعتاد

1010_{2} = 10

$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$ وهلم جرا. هذا يعني أنه يمكن تمثيل 2 مرفوعًا لأي قوة على أنها اثنين مرفوعات من صفر إلى 6 باستخدام عملية الحصول على باقي القسمة على 7 في حالة وجود قوة موجبة وصيغة بسيطة $2^{-x}=2^{(7-(x\: mod\:7))}$ إذا كان الأس عددًا سالبًا

في الواقع ، إذا تذكرنا خاصية ضرب الدرجات ، فسيتم تبسيط ضرب الأعداد بشكل كبير. ولضرب 6 في 3 ، ننظر الآن إلى الدرجة الثانية التي تساوي 6 وإلى أي درجة تساوي الثانية 3 ، أضف الأسس وانظر النتيجة - اثنان إلى حد ما ، والتي يمكن تمثيلها على أنها 2 أس من 0 إلى 6 مثال:

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

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

مع التقسيم ، يصبح كل شيء واضحًا جدًا أيضًا:

3 / 6 = 2^{3} / 2^{4} = 2^{(3 - 4)} = 2^{- 1} = 2^{(7 - (1 m o d 7))} = 2^{6} = 5

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

ويبدو أن هذا هو! سعادة المبرمج هي تطبيق الحساب في مجال جالوا - سطرين من التعليمات البرمجية ، لا داعي للقلق مع كثيرات الحدود ... نعم ، وسيكون أداء مثل هذا الرمز مرتفعًا ، ولكن بعد ذلك واجهت مشكلة أخرى: تم العثور على جدول القوى لاثنين في حقل GF [8] مع إنشاء متعدد الحدود 11 بسهولة. حتى هذا المورد. لكنني لم أقم بالبحث في جدول الدرجات لـ GF [256] على Google ، لذلك قررت تجميعها بنفسي ، سيساعدني C #. اضطررت إلى تطبيق خوارزمية الضرب وفقًا لقواعد كثيرات الحدود.

فيما يلي دالة ضرب عملية لـ GF [2 ^ n] مع كثير حدود عشوائي. التقييد - أستخدم العمليات الحسابية ذات 32 بت ، لذا يجب أن تكون قيمة n أقل من 16. كما تمت إضافة دالة هنا أيضًا للعثور على رقم البت الأكثر أهمية في الرقم

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;
}

الآن ، باستخدام الدالة أعلاه ، يمكنك إنشاء جدول قوى اثنين لـ GF الذي أحتاجه [256] وكتابة وحدة حساب Galois لـ stm32 باستخدام جدولين من 256 لكل منهما - أحدهما للمباشر والثاني لتحويل الرقم إلى أسه. لم أبدأ حتى في تنفيذ ترميز Reed-Solomon حتى الآن ، ولكن عندما يكون جاهزًا ، أعتقد أنني سأشاركه هنا. نأمل أن تكون أقصر.

تنفيذ برمجيات الضرب في حقول جالوا

More articles: