رمز الموسع

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
📷 يحتوي على 94 صور
الموسوعة الحرة

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

رموز الموسع

في نظرية الترميز ، يُعد رمز التوسيع...[ن،ن-م]2{\displaystyle [n,nm]_{2}\,}رمز الكتلة الخطي الذي تكون مصفوفة فحص التكافؤ فيه هي مصفوفة التجاور لرسم بياني ثنائي الأجزاء موسع . تتميز هذه الرموز بمسافة نسبية جيدة2(1-ε)γ{\displaystyle 2(1-\varepsilon )\gamma \,}، أينε{\displaystyle \varepsilon \,}وγ{\displaystyle \gamma \,}هي خصائص الرسم البياني الموسع كما هو محدد لاحقًا، المعدل(1-من){\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}وقابلية فك التشفير (خوارزميات وقت التشغيل)يا(ن){\displaystyle O(n)\,}يخرج).

تعريف

يتركب{\displaystyle B}كن(ج،د){\displaystyle (c,d)}- رسم بياني ثنائي الانتظام بين مجموعة منن{\displaystyle n}العقد{v1،⋯،vن}{\displaystyle \{v_{1},\cdots ,v_{n}\}}، وتسمى متغيرات ، ومجموعة منجن/د{\displaystyle cn/d}العقد{ج1،⋯،ججن/د}{\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}، وتسمى القيود .

يتركب(أنا،ج){\displaystyle b(i,j)}أن تكون دالة مصممة بحيث، لكل قيدجأنا{\displaystyle C_{i}}المتغيرات المجاورةجأنا{\displaystyle C_{i}}نكونvب(أنا،1)،⋯،vب(أنا،د){\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}.

يتركS{\displaystyle {\mathcal {S}}}ليكن رمز تصحيح الأخطاء بطول الكتلةد{\displaystyle d}رمز الموسعج(ب،S){\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}هو رمز طول الكتلةن{\displaystyle n}كلماتهم السرية هي الكلمات(x1،⋯،xن){\displaystyle (x_{1},\cdots ,x_{n})}بحيث يكون، من أجل1≤أنا≤جن/د{\displaystyle 1\leq i\leq cn/d}،(xب(أنا،1)،⋯،xب(أنا،د)){\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}هي كلمة سرية لـS{\displaystyle {\mathcal {S}}}[ 1 ]​

لقد ثبت وجود رسوم بيانية موسعة غير تافهة وخالية من الفقد. علاوة على ذلك، يمكننا بناؤها بشكل صريح. [ 2 ]

معدل

معدلج{\displaystyle C\,}حجم مصفوفة فحص التكافؤ هو حجمها مقسومًا على طول كتلتها. في هذه الحالة، يكون حجم مصفوفة فحص التكافؤ هو حجمم×ن{\displaystyle m\times n\,}وبالتاليج{\displaystyle C\,}لديه معدل على الأقل(ن-م)/ن=1-م/ن{\displaystyle (nm)/n=1-m/n\,}.

مسافة

يفترضε<12{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}ثم المسافة بين(ن،م،د،γ،1-ε){\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}رمز الموسعج{\displaystyle C\,}هو على الأقل2(1-ε)γن{\displaystyle 2(1-\varepsilon )\gamma n\,}.

دليل

لاحظ أنه يمكننا اعتبار كل كلمة رمزيةج{\displaystyle c\,}فيج{\displaystyle C\,}كمجموعة فرعية من الرؤوسS⊂ل{\displaystyle S\subset L\,}، بقول ذلك الرأسvأنا∈S{\displaystyle v_{i}\in S\,}إذا وفقط إذاأنا{\displaystyle i\,}إذا كان الرقم في فهرس كلمة الشفرة هو 1، فإنج{\displaystyle c\,}كلمة رمزية إذا كان كل رأسv∈R{\displaystyle v\in R\,}يقع بجوار عدد زوجي من الرؤوس فيS{\displaystyle S\,}(لكي تكون كلمة سر،جP=0{\displaystyle cP=0\,}، أينP{\displaystyle P\,}هي مصفوفة فحص التكافؤ. ثم، كل رأس فيR{\displaystyle R\,}يتوافق مع كل عمود منP{\displaystyle P\,}. ضرب المصفوفات علىجي إف(2)={0،1}{\displaystyle {\text{GF}}(2)=\{0,1\}\,}ثم يعطي النتيجة المرجوة. لذا، إذا كان رأسv∈R{\displaystyle v\in R\,}مجاور لرأس واحد فيS{\displaystyle S\,}، نعرف على الفور أنج{\displaystyle c\,}ليست كلمة سرية. دعشمال(S){\displaystyle N(S)\,}يشير إلى الجيران فيR{\displaystyle R\,}لS{\displaystyle S\,}، ويو(S){\displaystyle U(S)\,}يشير إلى جيرانS{\displaystyle S\,}والتي تكون فريدة، أي مجاورة لرأس واحد منS{\displaystyle S\,}.

اللمة 1

لكلS⊂ل{\displaystyle S\subset L\,}من الحجم|S|≤γن{\displaystyle |S|\leq \gamma n\,}،د|S|≥|شمال(S)|≥|يو(S)|≥د(1-2ε)|S|{\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}.

دليل

بشكل تافه،|شمال(S)|≥|يو(S)|{\displaystyle |N(S)|\geq |U(S)|\,}، منذv∈يو(S){\displaystyle v\in U(S)\,}يشير إلىv∈شمال(S){\displaystyle v\in N(S)\,}. |شمال(S)|≤د|S|{\displaystyle |N(S)|\leq d|S|\,}ويتبع ذلك لأن درجة كل رأس فيS{\displaystyle S\,}يكوند{\displaystyle d\,}بحسب خاصية التوسع للرسم البياني، يجب أن تكون هناك مجموعة مند(1-ε)|S|{\displaystyle d(1-\varepsilon )|S|\,}الحواف التي تصل إلى رؤوس مميزة. المتبقيدε|S|{\displaystyle d\varepsilon |S|\,}الحواف لا تشكل أكثر من ذلكدε|S|{\displaystyle d\varepsilon |S|\,}الجيران ليسوا فريدين، لذلكيو(S)≥د(1-ε)|S|-دε|S|=د(1-2ε)|S|{\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}.

نتيجة

كل صغير بما فيه الكفايةS{\displaystyle S\,}له جار فريد. وهذا يتبع لأنε<12{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}.

اللمة 2

كل مجموعة فرعيةتي⊂ل{\displaystyle T\subset L\,}مع|تي|<2(1-ε)γن{\displaystyle |T|<2(1-\varepsilon )\gamma n\,}له جار فريد من نوعه.

دليل

تثبت اللمة 1 الحالة|تي|≤γن{\displaystyle |T|\leq \gamma n\,}لنفترض2(1-ε)γن>|تي|>γن{\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}. يتركS⊂تي{\displaystyle S\subset T\,}بحيث|S|=γن{\displaystyle |S|=\gamma n\,}بحسب اللمة 1، نعلم أن|يو(S)|≥د(1-2ε)|S|{\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}ثم رأسv∈يو(S){\displaystyle v\in U(S)\,}هو فييو(تي){\displaystyle U(T)\,}لوv∉شمال(تي∖S){\displaystyle v\notin N(T\setminus S)\,}ونحن نعلم ذلك|تي∖S|≤2(1-ε)γن-γن=(1-2ε)γن{\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}إذن، من خلال الجزء الأول من اللمة 1، نعلم|شمال(تي∖S)|≤د(1-2ε)γن{\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}. منذε<12{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}،|يو(تي)|≥|يو(S)∖شمال(تي∖S)|≥|يو(S)|-|شمال(تي∖S)|>0{\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}وبالتالييو(تي){\displaystyle U(T)\,}ليس فارغًا.

نتيجة

لاحظ أنه إذا كان أتي⊂ل{\displaystyle T\subset L\,}لديه جار واحد فريد على الأقل، أي|يو(تي)|>0{\displaystyle |U(T)|>0\,}ثم الكلمة المقابلةج{\displaystyle c\,}بما يتوافق معتي{\displaystyle T\,}لا يمكن أن تكون كلمة رمزية، لأنها لن تُضرب في متجه الأصفار بواسطة مصفوفة فحص التكافؤ. بناءً على الحجة السابقة،ج∈ج⟹wت(ج)≥2(1-ε)γن{\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}. منذج{\displaystyle C\,}إذا كانت العلاقة خطية، نستنتج أنج{\displaystyle C\,}المسافة على الأقل2(1-ε)γن{\displaystyle 2(1-\varepsilon )\gamma n\,}.

التشفير

يُحدَّد وقت التشفير لرمز التوسيع بحد أقصى هو وقت التشفير لرمز خطي عام -يا(ن2){\displaystyle O(n^{2})\,}عن طريق ضرب المصفوفات. تُظهر نتيجة منسوبة إلى سبيلمان أن التشفير ممكن فييا(ن){\displaystyle O(n)\,}الوقت. [ 3 ]

فك التشفير

فك تشفير رموز الموسع ممكن فييا(ن){\displaystyle O(n)\,}الوقت عندماε<14{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}باستخدام الخوارزمية التالية.

يتركvأنا{\displaystyle v_{i}\,}ليكن رأسل{\displaystyle L\,}وهذا يتوافق معأنا{\displaystyle i\,}فهرس في الكلمات المشفرة لـج{\displaystyle C\,}. يتركy∈{0،1}ن{\displaystyle y\in \{0,1\}^{n}\,}أن تكون كلمة متداولة، وV(y)={vأنا|ال أناذ منصب y هو 1}{\displaystyle V(y)=\{v_{i}\mid {\text{الموضع }}i^{\text{ لـ }}y{\text{ هو }}1\}\,}. يتركهـ(أنا){\displaystyle e(i)\,}يكون|{v∈R|vأنا∈شمال(v) و شمال(v)∩V(y) بل إنه كذلك}|{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ و }}N(v)\cap V(y){\text{ زوجي}}\}|\,}، وo(أنا){\displaystyle o(i)\,}يكون|{v∈R|vأنا∈شمال(v) و شمال(v)∩V(y) غريب}|{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ و }}N(v)\cap V(y){\text{ فردي}}\}|\,}ثم لننظر في الخوارزمية الجشعة :

المدخلات: الكلمة المستلمةy{\displaystyle y\,}.

قم بتهيئة y' إلى y بينما يوجد av في R مجاور لعدد فردي من الرؤوس في V(y') إذا كان هناك عدد صحيح i بحيث يكون o(i) > e(i) اقلب المدخل i في y' آخر يفشل

الناتج: فشل، أو كلمة رمز معدلةy′{\displaystyle y'\,}.

دليل

نوضح أولاً صحة الخوارزمية، ثم نفحص وقت تشغيلها.

الصواب

يجب أن نُثبت أن الخوارزمية تنتهي بكلمة الترميز الصحيحة عندما تكون كلمة الترميز المُستلمة ضمن نصف المسافة بين كلمة الترميز الأصلية وكلمة الترميز الصحيحة. لنفترض أن مجموعة المتغيرات المُشوَّهة هيS{\displaystyle S\,}،s=|S|{\displaystyle s=|S|\,}ومجموعة الرؤوس غير المُرضية (المجاورة لعدد فردي من الرؤوس) فيR{\displaystyle R\,}يكونج{\displaystyle c\,}ستكون اللمة التالية مفيدة.

اللمة 3

لو0<s<γن{\displaystyle 0<s<\gamma n\,}ثم هناكvأنا{\displaystyle v_{i}\,}معo(أنا)>هـ(أنا){\displaystyle o(i)>e(i)\,}.

دليل

بحسب اللمة 1، نعلم أنيو(S)≥د(1-2ε)s{\displaystyle U(S)\geq d(1-2\varepsilon )s\,}لذا فإن متوسط ​​عدد الرؤوس في الشكل الهندسي يبلغ على الأقلد(1-2ε)>د/2{\displaystyle d(1-2\varepsilon )>d/2\,}الجيران الفريدون (تذكر أن الجيران الفريدين غير راضين، وبالتالي يساهمون فيo(أنا){\displaystyle o(i)\,})، منذε<14{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}وبالتالي يوجد رأسvأنا{\displaystyle v_{i}\,}معo(أنا)>هـ(أنا){\displaystyle o(i)>e(i)\,}.

لذا، إذا لم نصل بعد إلى كلمة رمزية، فسيكون هناك دائمًا رأس ما يجب قلبه. بعد ذلك، سنبين أن عدد الأخطاء لا يمكن أن يزيد أبدًا عنγن{\displaystyle \gamma n\,}.

اللمة 4

إذا بدأنا بـs<γ(1-2ε)ن{\displaystyle s<\gamma (1-2\varepsilon )n\,}إذن لن نصل أبداًs=γن{\displaystyle s=\gamma n\,}في أي نقطة من الخوارزمية.

دليل

عندما نقلب رأسًاvأنا{\displaystyle v_{i}\,}،o(أنا){\displaystyle o(i)\,}وهـ(أنا){\displaystyle e(i)\,}يتم تبادلها، وبما أننا كناo(أنا)>هـ(أنا){\displaystyle o(i)>e(i)\,}وهذا يعني أن عدد الرؤوس غير المُرضية على اليمين يتناقص بمقدار رأس واحد على الأقل بعد كل انقلاب.s<γ(1-2ε)ن{\displaystyle s<\gamma (1-2\varepsilon )n\,}، يكون العدد الأولي للرؤوس غير المُرضية على الأكثردγ(1-2ε)ن{\displaystyle d\gamma (1-2\varepsilon )n\,}، بحسب الرسم البيانيد{\displaystyle d\,}-الانتظام. إذا وصلنا إلى سلسلة نصية معγن{\displaystyle \gamma n\,}إذا كانت هناك أخطاء، فبحسب المبرهنة 1، سيكون هناك على الأقل دγ(1-2ε)ن{\displaystyle d\gamma (1-2\varepsilon )n\,}جيران فريدون، مما يعني أنه سيكون هناك على الأقلدγ(1-2ε)ن{\displaystyle d\gamma (1-2\varepsilon )n\,}الرؤوس غير المُرضية، وهذا تناقض.

تُظهر لنا اللمتان 3 و4 أنه إذا بدأنا بـs<γ(1-2ε)ن{\displaystyle s<\gamma (1-2\varepsilon )n\,}(نصف المسافة)ج{\displaystyle C\,})، عندها سنجد دائمًا رأسًاvأنا{\displaystyle v_{i}\,}للقلب. كل قلب يقلل عدد الرؤوس غير المُرضية فيR{\displaystyle R\,}بفارق لا يقل عن 1، وبالتالي تنتهي الخوارزمية في أكثر منم{\displaystyle m\,}خطوات، وتنتهي عند كلمة رمزية ما، وفقًا للّمة 3. (لو لم تكن عند كلمة رمزية، لكان هناك رأس ما يجب قلبه). تُظهر لنا اللّمة 4 أنه لا يمكننا أبدًا أن نكون أبعد منγن{\displaystyle \gamma n\,}بعيدًا عن كلمة السر الصحيحة. نظرًا لأن كلمة السر لها مسافة2(1-ε)γن>γن{\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}(منذε<12{\displaystyle \varepsilon <{\tfrac {1}{2}}\,})، يجب أن تكون كلمة الرمز التي تنتهي عندها هي كلمة الرمز الصحيحة، لأن عدد انعكاسات البتات أقل من نصف المسافة (لذلك لم نكن لنقطع مسافة كافية للوصول إلى أي كلمة رمز أخرى).

تعقيد

سنوضح الآن أن الخوارزمية يمكنها تحقيق فك تشفير خطي. لنفترضنم{\displaystyle {\tfrac {n}{m}}\,}كن ثابتًا، ور{\displaystyle r\,}ليكن أعلى درجة لأي رأس فيR{\displaystyle R\,}. لاحظ أنر{\displaystyle r\,}وهو ثابت أيضاً بالنسبة للإنشاءات المعروفة.

  1. المعالجة المسبقة: تستغرقيا(مر){\displaystyle O(mr)\,}الوقت اللازم لحساب ما إذا كان كل رأس فيR{\displaystyle R\,}له عدد فردي أو زوجي من الجيران.
  2. المعالجة المسبقة 2: نأخذيا(دن)=يا(دمر){\displaystyle O(dn)=O(dmr)\,}الوقت اللازم لحساب قائمة الرؤوسvأنا{\displaystyle v_{i}\,}فيل{\displaystyle L\,}والتي لديهاo(أنا)>هـ(أنا){\displaystyle o(i)>e(i)\,}.
  3. في كل تكرار: نقوم ببساطة بإزالة العنصر الأول من القائمة. لتحديث قائمة الرؤوس الفردية/الزوجية فيR{\displaystyle R\,}كل ما نحتاجه هو التحديثيا(د){\displaystyle O(d)\,}نقوم بعد ذلك بتحديث المدخلات، بإضافة أو حذف ما يلزم.يا(در){\displaystyle O(dr)\,}المدخلات في قائمة الرؤوس فيل{\displaystyle L\,}مع وجود جيران فرديين أكثر من الجيران الزوجيين، يتم إدخالهم/إزالتهم حسب الحاجة. وبالتالي، تستغرق كل عملية تكراريا(در){\displaystyle O(dr)\,}وقت.
  4. كما ذُكر أعلاه، فإن العدد الإجمالي للتكرارات هو على الأكثرم{\displaystyle m\,}.

وهذا يعطي إجمالي وقت تشغيل قدرهيا(مدر)=يا(ن){\displaystyle O(mdr)=O(n)\,}الوقت، أيند{\displaystyle d\,}ور{\displaystyle r\,}هي ثوابت.

انظر أيضاً

ملحوظات

تستند هذه المقالة إلى ملاحظات دورة الدكتور فينكاتيسان جوروسوامي. [ 4 ]

مراجع

  1. ↑ سيبسر، م.؛ سبيلمان، د.أ. (1996). "رموز التوسيع". معاملات IEEE في نظرية المعلومات . 42 (6): 1710-1722 . doi : 10.1109/18.556667 .
  2. ↑ كاباليو، م.؛ رينغولد، أ.؛ فادان، س.؛ ويغدرسون، أ. (2002). "موصلات العشوائية وموسعات عديمة الفقد ذات الدرجة الثابتة" . وقائع ندوة ACM السنوية الرابعة والثلاثين حول نظرية الحوسبة STOC '02 . ACM. الصفحات 659-668 . doi : 10.1145/509907.510003 . ISBN  978-1-58113-495-7. S2CID 1918841 . 
  3. ↑ سبيلمان، د. (1996). "رموز تصحيح الأخطاء القابلة للترميز وفك الترميز في زمن خطي". معاملات IEEE في نظرية المعلومات . 42 (6): 1723-1731 . CiteSeerX 10.1.1.47.2736 . doi : 10.1109/18.556668 . 
  4. ↑ غورو سوامي، ف. (15 نوفمبر 2006). "المحاضرة 13: رموز التوسيع" (ملف PDF) . CSE 533: تصحيح الأخطاء . جامعة واشنطن.غورو سوامي، ف. (مارس 2010). "ملاحظات 8: رموز التوسيع وفك تشفيرها" (ملف PDF) . مقدمة في نظرية الترميز . جامعة كارنيجي ميلون.غورو سوامي، ف. (سبتمبر 2004). "مقال رأي: رموز تصحيح الأخطاء ورسوم بيانية موسعة" . أخبار ACM SIGACT . 35 (3): 25-41 . doi : 10.1145/1027914.1027924 . S2CID 17550280 .