متجهة إلى سينغلتون

في نظرية الترميز ، يُعد حد سينغلتون ، الذي سُمي على اسم عالم الرياضيات الأمريكي ريتشارد كولوم سينغلتون (1928-2007)، حدًا أعلى تقريبيًا نسبيًا لحجم رمز الكتلة العشوائي${\displaystyle C}$بطول الكتلة${\displaystyle n}$، مقاس${\displaystyle M}$والمسافة الدنيا${\displaystyle d}$. يُعرف أيضًا باسم جوشيباوند ^{[ 1 ]} الذي أثبته جوشي (1958) وحتى قبل ذلك من قبل كوماميا .

أقصر مسافة لمجموعة${\displaystyle C}$من الكلمات المشفرة ذات الطول${\displaystyle n}$يُعرَّف بأنه $${\displaystyle d=\min _{\{x,y\in C:x\neq y\}}d(x,y)}$$ أين${\displaystyle d(x,y)}$هي مسافة هامينغ بين${\displaystyle x}$و${\displaystyle y}$التعبير${\displaystyle A_{q}(n,d)}$يمثل الحد الأقصى لعدد الكلمات المشفرة الممكنة في${\displaystyle q}$رمز كتلة -ary بطول${\displaystyle n}$والمسافة الدنيا ${\displaystyle d}$.

ثم تنص حدود سينجلتون على ما يلي: $${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.}$$

لاحظ أولاً أن عدد${\displaystyle q}$الكلمات ذات الامتداد -ary${\displaystyle n}$يكون${\displaystyle q^{n}}$بما أن كل حرف في مثل هذه الكلمة يمكن أن يأخذ أحد${\displaystyle q}$قيم مختلفة، بغض النظر عن الأحرف المتبقية.

والآن لنبدأ${\displaystyle C}$كن تعسفيًا${\displaystyle q}$رمز الكتلة -ary للمسافة الدنيا${\displaystyle d}$من الواضح أن جميع الكلمات السرية${\displaystyle c\in C}$متميزة. إذا قمنا بثقب الكود عن طريق حذف الأول${\displaystyle d-1}$إذا كانت جميع حروف كل كلمة رمزية مختلفة، فيجب أن تظل جميع الكلمات الرمزية الناتجة مختلفة بشكل متبادل، لأن جميع الكلمات الرمزية الأصلية في${\displaystyle C}$يجب أن يكون لديك مسافة هامينغ على الأقل${\displaystyle d}$وبالتالي، فإن حجم الكود المُعدَّل هو نفسه حجم الكود الأصلي.

يبلغ طول كل من الكلمات المشفرة التي تم الحصول عليها حديثًا $${\displaystyle n-(d-1)=n-d+1,}$$ وبالتالي، يمكن أن يكون هناك على الأكثر${\displaystyle q^{n-d+1}}$منهم. منذ${\displaystyle C}$إذا كان هذا الحد تعسفيًا، فيجب أن يكون هذا الحد صحيحًا لأكبر رمز ممكن بهذه المعلمات، وبالتالي: ^{[ 2 ]}$${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$$

لو${\displaystyle C}$هو رمز خطي بطول كتلة${\displaystyle n}$الأبعاد${\displaystyle k}$والمسافة الدنيا${\displaystyle d}$على الحقل المنتهي مع${\displaystyle q}$إذا كانت العناصر، فإن الحد الأقصى لعدد الكلمات المشفرة هو${\displaystyle q^{k}}$ويترتب على ذلك حد سينغلتون: $${\displaystyle q^{k}\leq q^{n-d+1},}$$ لهذا السبب. $${\displaystyle k\leq n-d+1,}$$ والتي عادة ما تُكتب على النحو التالي ^{[ 3 ]}$${\displaystyle d\leq n-k+1.}$$

في حالة الترميز الخطي، يمكن الحصول على برهان مختلف لحد Singleton من خلال ملاحظة أن رتبة مصفوفة فحص التكافؤ هي${\displaystyle nk}$[ ^{4 ] ثمة} برهان بسيط آخر ينبع من ملاحظة أن صفوف أي مصفوفة مولدة في شكلها القياسي لها وزن لا يتجاوز${\displaystyle n-k+1}$.

يُستشهد عادةً بهذا الاستنتاج من قِبل سينغلتون (1964) ، إلا أنه سبق إثباته من قِبل جوشي (1958) . ويشير جوشي إلى أن كوماميا (1953) قد توصل إلى هذا الاستنتاج سابقًا باستخدام برهان أكثر تعقيدًا. كما يُشير ويلش (1988 ، ص 72) إلى الأمر نفسه فيما يتعلق بكوماميا (1953) .

تُسمى رموز الكتل الخطية التي تحقق المساواة في حد سينغلتون برموز MDS (القابلة للفصل بأقصى مسافة) . ومن أمثلة هذه الرموز تلك التي تحتوي فقط على${\displaystyle q}$الكلمات السرية (الكل-${\displaystyle x}$كلمة تعني${\displaystyle x\in \mathbb {F} _{q}}$وبالتالي تحقيق الحد الأدنى من المسافة${\displaystyle n}$)، الرموز التي تستخدم كامل${\displaystyle (\mathbb {F} _{q})^{n}}$(المسافة الدنيا 1)، والرموز ذات رمز التكافؤ الواحد (المسافة الدنيا 2) ورموزها الثنائية . وغالبًا ما تسمى هذه الرموز برموز MDS البسيطة .

في حالة الأبجديات الثنائية، لا توجد سوى رموز MDS بسيطة. ^{[ 5 ] [ 6 ]}

تشمل أمثلة رموز MDS غير البسيطة رموز ريد-سولومون وإصداراتها الموسعة. ^{[ 7 ] [ 8 ]}

تُعد رموز MDS فئة مهمة من رموز الكتل، لأنه بالنسبة لـ ثابت${\displaystyle n}$و${\displaystyle k}$تتمتع هذه الأنظمة بأكبر قدرات تصحيح الأخطاء واكتشافها. وهناك عدة طرق لتصنيف رموز MDS: ^{[ 9 ]}

يسمح آخر هذه التوصيفات، باستخدام متطابقات ماك ويليامز ، بصيغة صريحة لتوزيع الوزن الكامل لرمز MDS. ^{[ 10 ]}

• متجه جيلبرت-فارشاموف
• متوجه إلى غريسمر
• هامينغ باوند
• متجه إلى جونسون
• بلوتكين المقيد

• جوشي، د.د. (1958)، "ملاحظة حول الحدود العليا لرموز المسافة الدنيا"، المعلومات والتحكم ، 1 (3): 289-295 ، doi : 10.1016/S0019-9958(58)80006-6
• كوماميا، ي. (1953)، "تطبيق الرياضيات المنطقية على نظرية المعلومات"، وقائع المؤتمر الوطني الياباني الثالث للرياضيات التطبيقية : 437
• لينغ، سان؛ شينغ، تشاوبينغ (2004)، نظرية الترميز / دورة تمهيدية ، مطبعة جامعة كامبريدج، رقم ISBN 0-521-52923-9
• ماكويليامز، إف جيه ؛ سلون، إن جيه إيه (1977)، نظرية رموز تصحيح الأخطاء ، نورث هولاند، ص 33، 37 ، رقم ISBN  0-444-85193-3
• بليس، فيرا (1998)، مقدمة في نظرية رموز تصحيح الأخطاء (  الطبعة الثالثة)، وايلي إنترساينس، رقم ISBN 0-471-19047-0
• رومان، ستيفن (1992)، الترميز ونظرية المعلومات ، GTM ، المجلد  134، سبرينغر-فيرلاغ، ISBN 0-387-97812-7
• سينغلتون، آر سي (1964)، "رموز q-nary ذات المسافة القصوى"، معاملات IEEE لنظرية المعلومات ، 10 (2): 116-118 ، doi : 10.1109/TIT.1964.1053661
• فيرماني، إل آر (1996)، عناصر نظرية الترميز الجبري ، تشابمان وهول
• ويلش، دومينيك (1988)، الرموز والتشفير ، مطبعة جامعة أكسفورد، رقم ISBN 0-19-853287-3

• جيه إتش فان لينت (1992). مقدمة في نظرية الترميز . جي تي إم . المجلد  86 (  الطبعة الثانية). سبرينغر-فيرلاغ. ص 61. ISBN  3-540-54894-7.
• نيدررايتر، هارالد ؛ شينغ، تشاوبينغ (2001). "6. تطبيقات على نظرية الترميز الجبري". النقاط النسبية على المنحنيات فوق الحقول المنتهية. النظرية والتطبيقات . سلسلة محاضرات جمعية لندن الرياضية. المجلد  285. كامبريدج : مطبعة جامعة كامبريدج . ISBN 0-521-66543-4. Zbl 0971.11033 .