رمز ريد-مولر

الموسوعة الحرة

تُعدّ رموز ريد-مولر رموزًا لتصحيح الأخطاء تُستخدم في تطبيقات الاتصالات اللاسلكية، لا سيما في الاتصالات الفضائية البعيدة. [ 1 ] علاوة على ذلك، يعتمد معيار الجيل الخامس المقترح [ 2 ] على الرموز القطبية ذات الصلة الوثيقة [ 3 ] لتصحيح الأخطاء في قناة التحكم. ونظرًا لخصائصها النظرية والرياضية المواتية، فقد خضعت رموز ريد-مولر لدراسات مستفيضة في علوم الحاسوب النظرية . فعلى سبيل المثال، ثبت أنها تحقق سعة شانون تقاربًا على القنوات المتناظرة عديمة الذاكرة. [ 4 ] [ 5 ] [ 6 ] [ 7 ]

تُعمّم رموز ريد-مولر رموز ريد-سولومون ورمز والش -هادامارد . وهي رموز خطية كتلية قابلة للاختبار والفك محليًا ، وقابلة للفك على مستوى القوائم . هذه الخصائص تجعلها مفيدة بشكل خاص في تصميم البراهين القابلة للتحقق الاحتمالي .

تُعدّ رموز ريد-مولر التقليدية رموزًا ثنائية، ما يعني أن الرسائل وكلمات الترميز عبارة عن سلاسل ثنائية. عندما يكون r و m عددين صحيحين حيث 0 ≤ r ≤ m ، يُرمز لرمز ريد-مولر ذي المعاملات r و m بالرمز RM( r , m ). عند طلب ترميز رسالة تتكون من k بت، حيث  ك=∑أنا=0ر(مأنا){\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}عندئذٍ، ينتج رمز RM( r , m ) كلمة رمزية تتكون من 2m بت . 

سميت رموز ريد-مولر نسبة إلى ديفيد إي. مولر ، الذي اكتشف الرموز في عام 1954، [ 8 ] وإيرفينغ إس. ريد ، الذي اقترح أول خوارزمية فك تشفير فعالة. [ 9 ]

الوصف باستخدام كثيرات الحدود منخفضة الدرجة

يمكن وصف رموز ريد-مولر بعدة طرق مختلفة (لكنها متكافئة في النهاية). ويُعدّ الوصف القائم على كثيرات الحدود منخفضة الدرجة أنيقًا للغاية ومناسبًا بشكل خاص لتطبيقها كرموز قابلة للاختبار محليًا ورموز قابلة للفك محليًا . [ 10 ]

المشفر

يمكن أن يحتوي رمز الكتلة على وظيفة تشفير واحدة أو أكثرج:{0،1}ك→{0،1}ن{\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}رسائل الخرائطx∈{0،1}ك{\textstyle x\in \{0,1\}^{k}}إلى الكلمات السريةج(x)∈{0،1}ن{\textstyle C(x)\in \{0,1\}^{n}}يبلغ طول رسالة كود ريد - مولر RM( r , m )ك=∑أنا=0ر(مأنا){\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}وطول الكتلةن=2م{\displaystyle \textstyle n=2^{م}}تعتمد إحدى طرق تعريف ترميز لهذا الرمز على تقييم كثيرات الحدود متعددة الخطية ذات m متغير ودرجة إجمالية لا تتجاوز r . يمكن كتابة كل كثيرة حدود متعددة الخطية على الحقل المنتهي بعنصرين على النحو التالي: صج(Z1،...،Zم)=∑S⊆{1،...،م}|S|≤رجS⋅∏أنا∈SZأنا.{\displaystyle p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.} الZ1،...،Zم{\textstyle Z_{1},\dots ,Z_{m}}هي متغيرات متعددة الحدود، والقيمجS∈{0،1}{\textstyle c_{S}\in \{0,1\}}هي معاملات كثيرة الحدود. لاحظ أن هناك بالضبطك=∑أنا=0ر(مأنا){\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}المعاملات. وبناءً على ذلك، تتكون رسالة الإدخال منك{\textstyle k}قيمx∈{0،1}ك{\textstyle x\in \{0,1\}^{k}}والتي تُستخدم كمعاملات. وبهذه الطريقة، كل رسالةx{\textstyle x}ينتج عنه متعددة حدود فريدةصx{\textstyle p_{x}}في m متغيرات. لإنشاء كلمة التشفيرج(x){\textstyle C(x)}يقوم المُشفّر بتقييم متعدد الحدودصx{\textstyle p_{x}}في جميع النقاطZ=(Z1،...،Zم)∈{0،1}م{\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}}، حيث يتم أخذ متعددة الحدود مع الضرب والجمع modulo 2(صx(Z)تعديل2)∈{0،1}{\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}أي أن دالة التشفير تُعرَّف عبرج(x)=(صx(Z)تعديل2)Z∈{0،1}م.{\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}

حقيقة أن كلمة السرج(x){\displaystyle C(x)}يكفي لإعادة بناء فريدةx{\displaystyle x}وينتج ذلك عن استيفاء لاغرانج ، الذي ينص على أن معاملات متعددة الحدود تُحدد بشكل فريد عند إعطاء عدد كافٍ من نقاط التقييم.ج(0)=0{\displaystyle C(0)=0}وج(x+y)=ج(x)+ج(y)تعديل2{\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}يحتفظ بجميع الرسائلx،y∈{0،1}ك{\displaystyle x,y\in \{0,1\}^{k}}، الوظيفةج{\displaystyle C}هي دالة خطية . وبالتالي فإن كود ريد - مولر هو كود خطي .

مثال

بالنسبة للرمز RM( 2,4 ) ، تكون المعلمات كما يلي:

ر=2م=4ك=(42)+(41)+(40)=6+4+1=11ن=2م=16{\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}

يتركج:{0،1}11→{0،1}16{\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}لتكن دالة التشفير المعرفة للتو. لتشفير السلسلة x = 1 1010 010101 ذات الطول 11، يقوم المُشفِّر أولاً بإنشاء متعددة الحدودصx{\textstyle p_{x}}في 4 متغيرات:صx(Z1،Z2،Z3،Z4)=1+(1⋅Z1+0⋅Z2+1⋅Z3+0⋅Z4)+(0⋅Z1Z2+1⋅Z1Z3+0⋅Z1Z4+1⋅Z2Z3+0⋅Z2Z4+1⋅Z3Z4)=1+Z1+Z3+Z1Z3+Z2Z3+Z3Z4{\displaystyle {\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}}ثم يقوم بتقييم هذه المعادلة متعددة الحدود عند جميع نقاط التقييم الـ 16 (0101 تعنيZ1=0،Z2=1،Z3=0،Z4=1){\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}: صx(0000)=1،صx(٠٠٠١)=1،صx(0010)=0،صx(0011)=1،{\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;}

صx(0100)=1،صx(0101)=1،صx(0110)=1،صx(0111)=0،{\displaystyle p_{x}(0100)=1,\;p_{x}(0101)=1,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;}

صx(1000)=0،صx(1001)=0،صx(1010)=0،صx(1011)=1،{\displaystyle p_{x}(1000)=0,\;p_{x}(1001)=0,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;}

صx(1100)=0،صx(1101)=0،صx(1110)=1،صx(1111)=0.{\displaystyle p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=1,\;p_{x}(1111)=0\,.}ونتيجة لذلك، فإن C(1 1010 010101) = 1101 1110 0001 0010 صحيح.

جهاز فك التشفير

كما ذُكر سابقًا، يُمكن استخدام استيفاء لاغرانج لاسترجاع الرسالة بكفاءة من كلمة مشفرة. مع ذلك، يجب أن يعمل جهاز فك التشفير حتى لو كانت الكلمة المشفرة مُشوّهة في بعض المواضع، أي عندما تكون الكلمة المُستلمة مُختلفة عن أي كلمة مشفرة أخرى. في هذه الحالة، يُمكن أن تُساعد عملية فك التشفير المحلية.

تعتمد خوارزمية ريد على الخاصية التالية: تبدأ من كلمة الشفرة، وهي عبارة عن سلسلة من نقاط التقييم من متعددة حدود غير معروفةصx{\textstyle p_{x}}لF2[X1،X2،...،Xم]{\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}درجة علمية على الأكثرر{\textstyle r}التي تريد العثور عليها. قد يحتوي التسلسل على أي عدد من الأخطاء يصل إلى2م-ر-1-1{\textstyle 2^{m-r-1}-1}مشمول.

إذا أخذنا في الاعتبار حدًا واحدًاμ{\textstyle \mu }بأعلى درجةد{\textstyle d}فيصx{\textstyle p_{x}}واجمع كل نقاط تقييم متعددة الحدود حيث جميع المتغيرات فيμ{\textstyle \mu }إذا كانت قيمة المتغير الأول تساوي 0 أو 1، وقيمة جميع المتغيرات الأخرى تساوي 0، فستحصل على قيمة معامل المتغير الثاني (0 أو 1).μ{\textstyle \mu }فيصx{\textstyle p_{x}}(هناك2د{\textstyle 2^{d}}(مثل هذه النقاط). ويرجع ذلك إلى حقيقة أن جميع القواسم الأحادية الدنيا لـμ{\textstyle \mu }يظهر عددًا زوجيًا من المرات في المجموع، وفقطμ{\textstyle \mu }يظهر مرة واحدة.

لمراعاة احتمالية حدوث أخطاء، يمكنك أيضًا الإشارة إلى أنه يمكنك تثبيت قيمة المتغيرات الأخرى على أي قيمة. لذا، بدلاً من إجراء عملية الجمع مرة واحدة فقط للمتغيرات الأخرى غير الموجودة فيμ{\textstyle \mu }بقيمة صفر، افعل ذلك2م-د{\textstyle 2^{m-d}}يتم حساب عدد مرات كل قيمة ثابتة للمتغيرات الأخرى. إذا لم يكن هناك خطأ، يجب أن تساوي جميع هذه المجاميع قيمة المعامل المطلوب. تتلخص الخوارزمية هنا في اختيار أغلبية الإجابات كقيمة للمعامل المطلوب. إذا تجاوزت نسبة الأخطاء في الأقلية الحد الأقصى المسموح به، تفشل عملية فك التشفير نظرًا لوجود عدد كبير جدًا من الأخطاء في رمز الإدخال.

بمجرد حساب المعامل، إذا كانت قيمته 1، قم بتحديث الكود لإزالة الحد الأحاديμ{\textstyle \mu }من رمز الإدخال، ثم انتقل إلى الحد الأحادي التالي، بترتيب عكسي لدرجته.

مثال

لننظر إلى المثال السابق ونبدأ من الكود. معر=2،م=4{\textstyle r=2,m=4}يمكننا إصلاح خطأ واحد على الأكثر في الكود. لنفترض أن كود الإدخال هو 1101 1110 0001 0110 (هذا هو الكود السابق مع وجود خطأ واحد).

نعرف درجة متعددة الحدودصx{\textstyle p_{x}}هو على الأكثرر=2{\textstyle r=2}، نبدأ بالبحث عن حدّ أحادي من الدرجة الثانية.

  • μ=X3X4{\textstyle \mu =X_{3}X_{4}}
    • نبدأ بالبحث عن نقاط التقييم معX1=0،X2=0،X3∈{0،1}،X4∈{0،1}{\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}في الكود، يكون هذا: 1101 1110 0001 0110. المجموع الأول هو 1 (عدد فردي من 1).
    • نبحث عن نقاط تقييم معX1=0،X2=1،X3∈{0،1}،X4∈{0،1}{\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}في الكود، يكون هذا: 1101 1110 0001 0110. المجموع الثاني هو 1.
    • نبحث عن نقاط تقييم معX1=1،X2=0،X3∈{0،1}،X4∈{0،1}{\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}في الكود، يكون هذا: 1101 1110 0001 0110. المجموع الثالث هو 1.
    • نبحث عن نقاط تقييم معX1=1،X2=1،X3∈{0،1}،X4∈{0،1}{\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}في الكود، يكون هذا: 1101 1110 0001 0110. المجموع الثالث هو 0 (عدد زوجي من 1).

لا تتفق المجاميع الأربعة (لذا نعلم بوجود خطأ)، لكن تقرير الأقلية لا يتجاوز الحد الأقصى المسموح به للخطأ (1)، لذلك نأخذ تقرير الأغلبية ومعاملμ{\textstyle \mu }هو 1.

نقوم بإزالةμ{\textstyle \mu }من الكود السابق، تابع  : الكود  : 1101 1110 0001 0110، تقييمμ{\textstyle \mu }الرمز الحالي هو 0001000100010001، أما الرمز الجديد فهو 1100 1111 0000 0111

  • μ=X2X4{\textstyle \mu =X_{2}X_{4}}
    • 11 00 11 11 0000 0111. المجموع هو 0
    • 11 00 11 11 0000 0111. المجموع هو 0
    • 1100 1111 00 00 01 11. المجموع هو 1
    • 1100 1111 00 00 01 11. المجموع هو 0

تم اكتشاف خطأ واحد، المعامل يساوي صفرًا، لا يوجد تغيير في الكود الحالي.

  • μ=X1X4{\textstyle \mu =X_{1}X_{4}}
    • 11 00 1111 00 00 0111. المجموع هو 0
    • 11 00 1111 00 00 0111. المجموع هو 0
    • 1100 11 11 0000 01 11. المجموع هو 1
    • 1100 11 11 0000 01 11. المجموع هو 0

تم اكتشاف خطأ واحد، المعامل يساوي صفرًا، لا يوجد تغيير في الكود الحالي.

  • μ=X2X3{\textstyle \mu =X_{2}X_{3}}
    • 1 1 0 0 1 1 1 1 0000 0111. المجموع هو 1
    • 1 1 0 0 1 1 1 1 0000 0111. المجموع هو 1
    • 1100 1111 0 0 0 0 0 1 1 1. المجموع هو 1
    • 1100 1111 0 0 0 0 0 1 1 1. المجموع هو 0

تم اكتشاف خطأ واحد، المعامل يساوي 1، قيمةμ{\textstyle \mu }الرمز الحالي هو 0000 0011 0000 0011، أما الرمز الحالي فهو الآن 1100 1100 0000 0100.

  • μ=X1X3{\textstyle \mu =X_{1}X_{3}}
    • 1 1 0 0 1100 0 0 0 0 0100. المجموع هو 1
    • 1 1 0 0 1100 0 0 0 0 0100. المجموع هو 1
    • 1100 1 1 0 0 0000 0 1 0 0. المجموع هو 1
    • 1100 1 1 0 0 0000 0 1 0 0 . المجموع هو 0

تم اكتشاف خطأ واحد، المعامل يساوي 1، قيمةμ{\textstyle \mu }الرمز الحالي هو 0000 0000 0011 0011، وهو الآن 1100 1100 0011 0111.

  • μ=X1X2{\textstyle \mu =X_{1}X_{2}}
    • 1 100 1 100 0 011 0 111. المجموع هو 0
    • 1 1 00 1 1 00 0 0 11 0 1 11. المجموع هو 1
    • 11 0 0 11 0 0 00 1 1 01 1 1. المجموع هو 0
    • 110 0 110 0 001 1 011 1. المجموع هو 0

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

  • μ=X4{\textstyle \mu =X_{4}}
    • 11 00 1100 0011 0111. المجموع هو 0
    • 11 00 1100 0011 0111. المجموع هو 0
    • 1100 11 00 0011 0111. المجموع هو 0
    • 1100 11 00 0011 0111. المجموع هو 0
    • 1100 1100 00 11 0111. المجموع هو 0
    • 1100 1100 00 11 0111. المجموع هو 0
    • 1100 1100 0011 01 11. المجموع هو 1
    • 1100 1100 0011 01 11. المجموع هو 0

تم اكتشاف خطأ واحد، المعامل يساوي صفرًا، لا يوجد تغيير في الكود الحالي.

  • μ=X3{\textstyle \mu =X_{3}}
    • 1 1 0 0 1100 0011 0111. المجموع هو 1
    • 1 1 0 0 1100 0011 0111. المجموع هو 1
    • 1100 1 1 0 0 0011 0111. المجموع هو 1
    • 1100 1 1 0 0 0011 0111. المجموع هو 1
    • 1100 1100 0 0 1 1 0111. المجموع هو 1
    • 1100 1100 0 0 1 1 0111. المجموع هو 1
    • 1100 1100 0011 0 1 1 1. المجموع هو 1
    • 1100 1100 0011 0111. Sum is 0

One error detected, coefficient is 1, valuation of μ{\textstyle \mu } is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100.

Then we'll find 0 for μ=X2{\textstyle \mu =X_{2}}, 1 for μ=X1{\textstyle \mu =X_{1}} and the current code become 1111 1111 1111 1011.

For the degree 0, we have 16 sums of only 1 bit. The minority is still of size 1, and we found px=1+X1+X3+X1X3+X2X3+X3X4{\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}} and the corresponding initial word 1 1010 010101

Generalization to larger alphabets via low-degree polynomials

Using low-degree polynomials over a finite field F{\displaystyle \mathbb {F} } of size q{\displaystyle q}, it is possible to extend the definition of Reed–Muller codes to alphabets of size q{\displaystyle q}. Let m{\displaystyle m} and d{\displaystyle d} be positive integers, where m{\displaystyle m} should be thought of as larger than d{\displaystyle d}. To encode a message x∈Fk{\textstyle x\in \mathbb {F} ^{k}} of width k=(m+dm){\displaystyle k=\textstyle {\binom {m+d}{m}}}, the message is again interpreted as an m{\displaystyle m}-variate polynomial px{\displaystyle p_{x}} of total degree at most d{\displaystyle d} and with coefficient from F{\displaystyle \mathbb {F} }. Such a polynomial indeed has (m+dm){\displaystyle \textstyle {\binom {m+d}{m}}} coefficients. The Reed–Muller encoding of x{\displaystyle x} is the list of all evaluations of px(a){\displaystyle p_{x}(a)} over all a∈Fm{\displaystyle a\in \mathbb {F} ^{m}}. Thus the block length is n=qm{\displaystyle n=q^{m}}.

Description using a generator matrix

A generator matrix for a Reed–Muller code RM(r, m) of length N = 2m can be constructed as follows. Let us write the set of all m-dimensional binary vectors as:

X=F2m={x1,…,xN}.{\displaystyle X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}

We define in N-dimensional space F2N{\displaystyle \mathbb {F} _{2}^{N}} the indicator vectors

IA∈F2N{\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{N}}

on subsets A⊂X{\displaystyle A\subset X} by:

(IA)i={1 if xi∈A0 otherwise{\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}}

together with, also in F2N{\displaystyle \mathbb {F} _{2}^{N}}, the binary operation

w∧z=(w1⋅z1,…,wN⋅zN),{\displaystyle w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),}

referred to as the wedge product (not to be confused with the wedge product defined in exterior algebra). Here, w=(w1,w2,…,wN){\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})} and z=(z1,z2,…,zN){\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})} are points in F2N{\displaystyle \mathbb {F} _{2}^{N}} (N-dimensional binary vectors), and the operation ⋅{\displaystyle \cdot } is the usual multiplication in the field F2{\displaystyle \mathbb {F} _{2}}.

F2m{\displaystyle \mathbb {F} _{2}^{m}} is an m-dimensional vector space over the field F2{\displaystyle \mathbb {F} _{2}}, so it is possible to write

(F2)m={(ym,…,y1)∣yi∈F2}.{\displaystyle (\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.}

We define in N-dimensional space F2N{\displaystyle \mathbb {F} _{2}^{N}} the following vectors with length N:v0=(1,1,…,1){\displaystyle N:v_{0}=(1,1,\ldots ,1)} and

vi=IHi,{\displaystyle v_{i}=\mathbb {I} _{H_{i}},}

where 1 ≤ i ≤ m and the Hi are hyperplanes in (F2)m{\displaystyle (\mathbb {F} _{2})^{m}} (with dimension m− 1):

Hi={y∈(F2)m∣yi=0}.{\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.}

The generator matrix

إنّ رمز ريد - مولر RM( r , m ) من الرتبة r والطول N  =  2m هو الرمز الناتج عن v₀ وحاصل الضرب الخارجي حتى r من المتجهات vᵢ ، حيث 1 ≤ i ≤ m (حيث يُعتبر حاصل الضرب الخارجي لأقل من متجه واحد، وفقًا للعرف ، هوية العملية). بعبارة أخرى، يمكننا بناء مصفوفة مولدة لرمز RM( r , m ) باستخدام المتجهات وتباديل حاصل الضرب الخارجي الخاصة بها حتى r في كل مرة.v0،v1،...،vن،...،(vأنا1∧vأنا2)،...(vأنا1∧vأنا2...∧vأنار){\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}}، كصفوف مصفوفة المولد، حيث 1 ≤ i k ≤ m .

المثال 1

لنفترض أن m = 3. إذن N = 8، و

X=F23={(0،0،0)،(0،0،1)،(0،1،0)...،(1،1،1)}،{\displaystyle X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),(0,1,0)\ldots ,(1,1,1)\},}

و

v0=(1،1،1،1،1،1،1،1)v1=(1،0،1،0،1،0،1،0)v2=(1،1،0،0،1،1،0،0)v3=(1،1،1،1،0،0،0،0).{\displaystyle {\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}}

يتم توليد رمز RM(1,3) بواسطة المجموعة

{v0،v1،v2،v3}،{\displaystyle \{v_{0},v_{1},v_{2},v_{3}\},\,}

أو بشكل أكثر وضوحاً من خلال صفوف المصفوفة:

(11111111101010101100110011110000){\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\end{pmatrix}}}

المثال 2

يتم توليد رمز RM(2,3) بواسطة المجموعة:

{v0،v1،v2،v3،v1∧v2،v1∧v3،v2∧v3}{\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}

أو بشكل أكثر وضوحاً من خلال صفوف المصفوفة:

(11111111101010101100110011110000100010001010000011000000){\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}}

ملكيات

تنطبق الخصائص التالية:

  1. تشكل مجموعة جميع نواتج الضرب الإسفيني الممكنة حتى m من v i أساسًا لـF2شمال{\displaystyle \mathbb {F} _{2}^{N}}.
  2. رمز RM ( r , m ) له رتبة
    ∑s=0ر(مs).{\displaystyle \sum _{s=0}^{r}{m \choose s}.}
  3. RM ( r , m ) = RM ( r , m − 1) | RM ( r − 1, m − 1) حيث يشير الرمز '|' إلى حاصل الضرب الشريطي لرمزين.
  4. RM ( r , m ) له وزن هامينغ الأدنى 2 m − r .

يُعدّ التوزيع الكامل لأوزان الكلمات المشفرة أكثر تعقيدًا من صيغة المسافة الدنيا. وقد درس تاداو كاسامي ونوبوكي توكورا بنية أوزان رموز ريد-مولر، بما في ذلك الكلمات المشفرة ذات الوزن المنخفض التي تتجاوز الحد الأدنى للوزن. [ 11 ]

دليل

  1. هناك
    ∑s=0م(مs)=2م=شمال{\displaystyle \sum _{s=0}^{m}{m \choose s}=2^{m}=N}

    هذه المتجهات وF2شمال{\displaystyle \mathbb {F} _{2}^{N}}بما أن لها بُعدًا N ، يكفي التحقق من أن المتجهات N تولد فضاءً ممتدًا؛ أو بعبارة أخرى، يكفي التحقق من أنRم(م،م)=F2شمال{\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}}.

    ليكن x متجهًا ثنائيًا طوله m ، وهو عنصر من X. ولتكن ( x ) i العنصر i من x . عرّف

    yأنا={vأنا لو (x)أنا=0v0+vأنا لو (x)أنا=1{\displaystyle y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}}

    حيث 1 ≤ i ≤ m .

    ثمأنا{x}=y1∧⋯∧yم{\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}

    يؤدي التوسع عبر خاصية توزيع الضرب الخارجي إلىأنا{x}∈Rم(م،م){\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)}ثم بما أن المتجهات{أنا{x}|x∈X}{\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}}فترةF2شمال{\displaystyle \mathbb {F} _{2}^{N}}لديناRم(م،ن)=F2شمال{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}.
  2. بحسب 1 ، يجب أن تكون جميع منتجات الوتد هذه مستقلة خطيًا، لذا فإن رتبة RM( r, m ) يجب أن تكون ببساطة عدد هذه المتجهات.
  3. تم حذفه.
  4. بالاستقراء.
    رمز RM ( 0 , m )  هو رمز تكرار بطول N  = 2 m ووزن N = 2 m − 0 = 2 m − r .Rم(م،ن)=F2ن{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}وله وزن 1 = 2 0 = 2 m − r .

    تُقدّم مقالة "الضرب الشريطي " (في نظرية الترميز) برهانًا على أن وزن الضرب الشريطي لرمزين C1 و C2 يُعطى بالصيغة التالية :

    مين{2w(ج1)،w(ج2)}{\displaystyle \min\{2w(C_{1}),w(C_{2})\}}
    إذا كان 0 < r < m وإذا
    1.   RM ( r , m − 1) له وزن 2m − 1 − r
    2.     وزن RM( r − 1, m − 1) هو 2m − 1 − ( r − 1 ) = 2m − r
    إذن، يكون للمنتج الصلب وزن.
    مين{2×2م-1-ر،2م-ر}=2م-ر.{\displaystyle \min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.}

فك تشفير رموز RM

يمكن فك تشفير رموز RM( r , m ) باستخدام فك التشفير المنطقي للأغلبية . تقوم فكرة فك التشفير المنطقي للأغلبية على إنشاء عدة مجاميع اختبارية لكل عنصر من عناصر كلمة الرمز المستلمة. بما أن جميع المجاميع الاختبارية المختلفة يجب أن تكون لها نفس القيمة (أي قيمة وزن عنصر كلمة الرسالة)، يمكننا استخدام فك التشفير المنطقي للأغلبية لفك تشفير قيمة عنصر كلمة الرسالة. بمجرد فك تشفير كل رتبة من رتب متعددة الحدود، يتم تعديل الكلمة المستلمة وفقًا لذلك عن طريق إزالة كلمات الرمز المقابلة الموزونة بمساهمات الرسالة التي تم فك تشفيرها، حتى المرحلة الحالية. لذلك، بالنسبة لرمز RM من الرتبة r ، علينا فك التشفير بشكل تكراري r+1 مرة قبل أن نصل إلى كلمة الرمز النهائية المستلمة. كما يتم حساب قيم بتات الرسالة من خلال هذه الآلية؛ وأخيرًا، يمكننا حساب كلمة الرمز عن طريق ضرب كلمة الرسالة (التي تم فك تشفيرها للتو) في مصفوفة المولد.

من الدلائل على نجاح عملية فك التشفير، وجود كلمة مُعدّلة مُستلمة جميع قيمها أصفار، في نهاية عملية فك التشفير المكونة من ( r  + 1) مرحلة باستخدام منطق الأغلبية. وقد اقترح هذه التقنية إيرفينغ إس. ريد، وهي أكثر عمومية عند تطبيقها على رموز الهندسة المحدودة  الأخرى .

وصف باستخدام بنية تكرارية

يوجد رمز ريد-مولر RM( r,m ) لأي عددين صحيحينم≥0{\displaystyle m\geq 0}و0≤ر≤م{\displaystyle 0\leq r\leq m}. يُعرَّف RM( m , m ) بأنه الكون (2م،2م،1{\displaystyle 2^{m},2^{m},1}) رمز. يُعرَّف RM( − 1,m) بأنه الرمز التافه (2م،0،∞{\displaystyle 2^{m},0,\infty }يمكن إنشاء رموز RM المتبقية من هذه الرموز الأولية باستخدام طريقة مضاعفة الطول.

Rم(ر،م)={(u،u+v)|u∈Rم(ر،م-1)،v∈Rم(ر-1،م-1)}.{\displaystyle \mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.}

انطلاقًا من هذا البناء، فإن RM( r,m ) عبارة عن رمز كتلة خطي ثنائي ( n , k , d ) بطول n  =  2m ، وبُعدك(ر،م)=ك(ر،م-1)+ك(ر-1،م-1){\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}والمسافة الدنياد=2م-ر{\displaystyle d=2^{m-r}}لر≥0{\displaystyle r\geq 0}الشفرة الثنائية لـ RM( r,m ) هي RM( m - r - 1, m ). وهذا يُظهر أن شفرات التكرار وشفرات SPC هي شفرات ثنائية، وأن الشفرات المتعامدة ثنائية وشفرات هامينغ الموسعة هي شفرات ثنائية، وأن الشفرات التي يكون فيها k  = n /2  هي شفرات ثنائية ذاتية.

حالات خاصة من رموز ريد - مولر

جدول بجميع رموز RM(r,m) لـ m≤5

جميع رموز RM( r , m ) مع 0≤م≤5{\displaystyle 0\leq m\leq 5} يتم عرض حجم الأبجدية 2 هنا، مع شرح باستخدام تدوين نظرية الترميز القياسي [n,k,d] لرموز الكتل . الرمز RM( r , m )  هو[2م،ك،2م-ر]2{\displaystyle \textstyle [2^{m},k,2^{m-r}]_{2}}-code، أي أنه رمز خطي على أبجدية ثنائية ، وله طول كتلة2م{\displaystyle \textstyle 2^{m}}، طول الرسالة (أو بُعدها) k ، والمسافة الدنيا2م-ر{\displaystyle \textstyle 2^{m-r}}.

012345م
ZRM( m,m ) ( 2 m , 2 m , 1)رموز الكون
RM(5,5) (32,32,1)
RM(4,4) (16,16,1)RM( m − 1, m )    (2 m , 2 m − 1, 2)رموز SPC
RM(3,3) (8,8,1)RM(4,5) (32,31,2)
RM(2,2) (4,4,1)RM(3,4) (16,15,2)RM( m − 2, m )   (2 m , 2 m − m − 1, 4)رموز هامينغ الموسعة
RM(1,1) (2,2,1)RM(2,3) (8,7,2)RM(3,5) (32,26,4)
RM(0,0) (1,1,1)RM(1,2) (4,3,2)RM(2,4) (16,11,4)
RM(0,1) (2,1,2)RM(1,3) (8,4,4)RM(2,5) (32,16,8)RM( r , m =2 r +1) (2 2 r +1 , 2 2 r , 2 r +1 )رموز ذاتية الازدواجية
RM( − 1,0) (1,0,∞{\displaystyle \infty })RM(0,2) (4,1,4)RM(1,4) (16,5,8)
RM(−1,1) (2,0,∞{\displaystyle \infty })RM(0,3) (8,1,8)RM(1,5) (32,6,16)
RM(−1,2) (4,0,∞{\displaystyle \infty })RM(0,4) (16,1,16)RM(1, m ) (2 m , m +1, 2 m − 1 )رموز هادامارد المثقوبة
RM( − 1,3) (8,0,∞{\displaystyle \infty })RM(0,5) (32,1,32)
RM( − 1,4) (16,0,∞{\displaystyle \infty })RM(0, m ) (2 m , 1, 2 m )رموز التكرار
RM( − 1,5) (32,0,∞{\displaystyle \infty })
RM( − 1, m ) (2 m , 0, ∞ )رموز بسيطة

خصائص رموز RM(r,m) لـ r≤1 أو r≥m-2

  • رموز RM(0, m )  هي رموز تكرار بطول N  =  2 m ، ومعدلR=1شمال{\displaystyle {R={\tfrac {1}{N}}}}والمسافة الدنيادمين=شمال{\displaystyle d_{\min }=N}.
  • رموز RM(1, m )  هي رموز فحص التكافؤ بطول N  =  2 m ، ومعدلR=م+1شمال{\displaystyle R={\tfrac {m+1}{N}}}والمسافة الدنيادمين=شمال2{\displaystyle d_{\min }={\tfrac {N}{2}}}.
  • رموز RM( m − 1, m )    هي رموز فحص تكافؤ أحادي بطول N  =  2m ، معدلR=شمال-1شمال{\displaystyle R={\tfrac {N-1}{N}}}والمسافة الدنيادمين=2{\displaystyle d_{\min }=2}.
  • تُعدّ رموز RM( m − 2, m )    عائلة من رموز هامينغ الموسعة بطول N  =  2m ذات مسافة دنيادمين=4{\displaystyle d_{\min }=4}[ 12 ]​

مراجع

  1. ↑ ماسي، جيمس ل. (1992)، "الاتصالات والترميز في الفضاء السحيق: زواج مثالي"، أساليب متقدمة للاتصالات عبر الأقمار الصناعية والفضاء السحيق ، سلسلة محاضرات في علوم التحكم والمعلومات، المجلد  182، دار نشر سبرينغر، الصفحات 1-17 ، CiteSeerX 10.1.1.36.4265 ، doi : 10.1007/bfb0036046 ، ISBN   978-3540558514ملف PDF
  2. ↑ "التقرير النهائي لاجتماع 3GPP RAN1 رقم 87" . 3GPP . تم الاطلاع عليه بتاريخ 31 أغسطس 2017 .
  3. ↑ أريكان، إردال (2009). "استقطاب القناة: طريقة لبناء رموز تحقق السعة لقنوات متناظرة ثنائية الإدخال عديمة الذاكرة - مجلات IEEE". معاملات IEEE في نظرية المعلومات . 55 (7): 3051-3073 . arXiv : 0807.3917 . doi : 10.1109/TIT.2009.2021379 . hdl : 11693/11695 . S2CID 889822 . 
  4. ↑ آبي، إيمانويل؛ شبيلكا، أمير؛ ويغدرسون، آفي (14 يونيو 2015). رموز ريد-مولر للمحو العشوائي والأخطاء . ACM. ص 297-306 . doi : 10.1145/2746539.2746575 . ISBN  978-1-4503-3536-2تم الاطلاع عليه بتاريخ 12 نوفمبر 2025 .
  5. ↑ كوديكار، شرينيفاس؛ كومار، سانثوش؛ مونديلي، ماركو؛ فايستر، هنري د.؛ ساسوغلو، إيرين؛ أوربانك، ريديجر ل. (2017). "رموز ريد-مولر تحقق السعة على قنوات المحو" . معاملات IEEE في نظرية المعلومات . 63 (7): 4298-4316 . doi : 10.1109/TIT.2017.2673829 . ISSN 0018-9448 . تاريخ الاسترجاع: 12 نوفمبر 2025 . 
  6. ↑ ريفز، جالين؛ بفايستر، هنري د. (2024). "رموز ريد-مولر على قنوات BMS تحقق احتمالية خطأ بت متلاشية لجميع المعدلات الأقل من السعة" . معاملات IEEE في نظرية المعلومات . 70 (2): 920-949 . doi : 10.1109/TIT.2023.3286452 . ISSN 0018-9448 . تاريخ الاسترجاع: 12 نوفمبر 2025 . 
  7. ↑ آبي، إيمانويل؛ ساندون، كولين (2023-11-06). برهان على أن رموز ريد-مولر تحقق سعة شانون على القنوات المتناظرة . IEEE. ص 177-193 . doi : 10.1109/FOCS57990.2023.00020 . ISBN  979-8-3503-1894-4تم الاطلاع عليه بتاريخ 12 نوفمبر 2025 .
  8. ↑ مولر، ديفيد إي. (1954). "تطبيق الجبر البولياني على تصميم دوائر التبديل واكتشاف الأخطاء". معاملات المجموعة المهنية للحاسبات الإلكترونية التابعة لمعهد مهندسي الراديو . EC-3 (3): 6-12 . doi : 10.1109/irepgelc.1954.6499441 . ISSN 2168-1740 . 
  9. ↑ ريد، إيرفينغ س. (1954). "فئة من رموز تصحيح الأخطاء المتعددة ونظام فك التشفير". معاملات المجموعة المهنية لنظرية المعلومات التابعة لمعهد مهندسي الراديو . 4 (4): 38-49 . doi : 10.1109/tit.1954.1057465 . hdl : 10338.dmlcz/143797 . ISSN 2168-2690 . 
  10. ↑ براهلاد هارشا وآخرون، حدود خوارزميات التقريب: PCPs والألعاب الفريدة (ملاحظات محاضرات DIMACS التعليمية) ، القسم 5.2.1.
  11. ↑ كاسامي، تاداو؛ توكورا، نوبوكي (نوفمبر 1970). "حول بنية الأوزان لرموز ريد-مولر". معاملات IEEE في نظرية المعلومات . 16 (6): 752-759 . doi : 10.1109/TIT.1970.1054545 .
  12. ↑ Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.

للمزيد من القراءة