رمز البادئة

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

على سبيل المثال، رمز مع رمز${\displaystyle \{{\texttt {a}},{\texttt {bb}}\}}$له خاصية البادئة؛ رمز يتكون من${\displaystyle \{{\texttt {a}},{\texttt {b}},{\texttt {ab}},{\texttt {aa}}\}}$لا، لأن a هي بادئة لكل من ab و aa . الشفرة البادئة هي شفرة قابلة للفك بشكل فريد : فبإعطاء تسلسل كامل ودقيق، يستطيع جهاز الاستقبال تحديد كل كلمة دون الحاجة إلى علامة خاصة بين الكلمات. مع ذلك، توجد شفرات قابلة للفك بشكل فريد ليست شفرات بادئة؛ على سبيل المثال، معكوس الشفرة البادئة يظل قابلاً للفك بشكل فريد (فهو شفرة لاحقة)، ولكنه ليس بالضرورة شفرة بادئة.

تُعرف رموز البادئة أيضًا باسم الرموز الخالية من البادئة ، ورموز شرط البادئة ، والرموز الآنية . على الرغم من أن ترميز هوفمان هو مجرد واحد من العديد من الخوارزميات المستخدمة لاستخلاص رموز البادئة، إلا أن رموز البادئة تُعرف أيضًا باسم "رموز هوفمان"، حتى عندما لا يكون الرمز ناتجًا عن خوارزمية هوفمان. يُستخدم مصطلح " الرمز الخالي من الفواصل" أحيانًا كمرادف لمصطلح "الرموز الخالية من البادئة" ^{[ 1 ] [ 2 ]،} ولكن في معظم الكتب والمقالات الرياضية (مثل ^{[ 3 ] [ 4 ]} )، يُستخدم مصطلح "الرمز الخالي من الفواصل" للدلالة على الرمز ذاتي التزامن ، وهو نوع فرعي من رموز البادئة.

باستخدام رموز البادئة، يمكن إرسال الرسالة كسلسلة من الكلمات المشفرة المتصلة، دون أي علامات خارج النطاق أو (بدلاً من ذلك) علامات خاصة بين الكلمات لتحديدها في الرسالة. يستطيع المتلقي فك تشفير الرسالة بشكل لا لبس فيه، من خلال البحث المتكرر عن التسلسلات التي تُشكل كلمات مشفرة صحيحة وإزالتها. هذا غير ممكن عمومًا مع الرموز التي تفتقر إلى خاصية البادئة، على سبيل المثال${\displaystyle \{{\texttt {0}},{\texttt {1}},{\texttt {10}},{\texttt {11}}\}}$: لن يعرف جهاز الاستقبال الذي يقرأ الرقم 1 في بداية كلمة رمزية ما إذا كانت هذه هي كلمة الرمز الكاملة 1 ، أو مجرد بادئة كلمة الرمز 10 أو 11 ؛ لذلك يمكن تفسير السلسلة 10 إما على أنها كلمة رمزية واحدة أو على أنها سلسلة من الكلمات 1 ثم 0 .

تُعد رموز هوفمان ذات الطول المتغير ، ورموز البلد الهاتفية ، وأجزاء البلد والناشر من أرقام ISBN ، ورموز التزامن الثانوية المستخدمة في معيار UMTS W-CDMA 3G اللاسلكي، ومجموعات التعليمات (لغة الآلة) لمعظم البنى الدقيقة للحاسوب رموزًا بادئة.

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

لكل رمز قابل للفك بشكل فريد، يوجد رمز بادئ له نفس أطوال كلمات الرمز. ^{[ 5 ]} تُحدد متباينة كرافت مجموعات أطوال كلمات الرمز الممكنة في رمز قابل للفك بشكل فريد. ^{[ 6 ]}

إذا كانت جميع الكلمات في الشفرة متساوية الطول، تُسمى الشفرة شفرة ثابتة الطول ، أو شفرة كتلة (مع أن مصطلح شفرة الكتلة يُستخدم أيضًا لوصف شفرات تصحيح الأخطاء ثابتة الحجم في ترميز القنوات ). على سبيل المثال، يبلغ طول حروف ISO 8859-15 دائمًا 8 بتات. ويبلغ طول حروف UTF-32/UCS-4 دائمًا 32 بتًا. ويبلغ طول خلايا ATM دائمًا 424 بتًا (53 بايتًا).${\displaystyle k}$يمكن للبتات أن تشفر ما يصل إلى${\displaystyle 2^{k}}$رموز المصدر.

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

يُعدّ التشفير الثنائي المقتطع تعميمًا مباشرًا للرموز ذات الطول الثابت للتعامل مع الحالات التي لا يكون فيها عدد الرموز n قوةً للعدد اثنين. تُخصّص للرموز المصدر كلمات ترميز بطول${\displaystyle k}$و${\displaystyle k+1}$، أين${\displaystyle k}$يتم اختيارها بحيث${\displaystyle 2^{k}<n\leq 2^{k+1}}$.

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

تستخدم بعض الشفرات رمزًا خاصًا يُسمى "الفاصلة" (يُعرف أيضًا بالقيمة المرجعية )، وهو يختلف عن البيانات العادية. ^{[ 7 ]} يُشبه هذا إلى حد ما المسافات بين الكلمات في الجملة؛ فهي تُحدد نهاية كل كلمة وبداية أخرى. إذا انتهت كل كلمة مشفرة بفاصلة، ولم تظهر الفاصلة في أي مكان آخر ضمن الكلمة، فإن الشفرة تكون تلقائيًا خالية من البادئات. مع ذلك، قد يكون تخصيص رمز كامل لاستخدامه كفاصلة فقط غير فعال، خاصةً في اللغات ذات عدد الرموز القليل. تُعد شفرة مورس مثالًا شائعًا على شفرة متغيرة الطول تستخدم الفاصلة. تساعد الفواصل الطويلة بين الأحرف، والفواصل الأطول بين الكلمات، على تمييز نهاية كل حرف (أو كلمة) وبداية الكلمة التالية. وبالمثل، تستخدم شفرة فيبوناتشي الرقم 11 للدلالة على نهاية كل كلمة مشفرة.

الرموز ذاتية التزامن هي رموز بادئة تسمح بمزامنة الإطار .

رمز اللاحقة هو مجموعة من الكلمات لا تُعدّ أيٌّ منها لاحقةً لأيّ كلمة أخرى؛ أو بعبارة أخرى، هي مجموعة من الكلمات تُمثّل عكس رمز البادئة. وكما هو الحال مع رمز البادئة، فإنّ تمثيل سلسلة نصية كسلسلة من هذه الكلمات يكون فريدًا. رمز البادئة المزدوجة هو مجموعة من الكلمات التي تُمثّل رمز بادئة ولاحقة في آنٍ واحد. ^{[ 8 ]} رمز البادئة الأمثل هو رمز بادئة ذو طول متوسط ​​أدنى. أي، لنفترض أبجدية من n رمزًا باحتمالات${\displaystyle p(A_{i})}$بالنسبة لرمز البادئة C. إذا كان C' رمز بادئة آخر و${\displaystyle \lambda '_{i}}$إذا كانت أطوال الكلمات المشفرة لـ C' هي ، فإن$\displaystyle \sum _{i=1}^{n}{\lambda _{i}p(A_{i})}\leq \sum _{i=1}^{n}{\lambda '_{i}p(A_{i})}\!}$[ ^{9 ]​}

تتضمن أمثلة رموز البادئة ما يلي:

• رموز هوفمان ذات الطول المتغير
• رموز الاتصال الهاتفية للدول
• ترميز تشين-هو
• أجزاء البلد والناشر من أرقام ISBN
• رموز المزامنة الثانوية المستخدمة في معيار UMTS W-CDMA 3G اللاسلكي
• رموز VCR Plus+
• تنسيق تحويل Unicode ، وخاصة نظام UTF-8 لترميز أحرف Unicode ، وهو عبارة عن رمز خالٍ من البادئات ورمز متزامن ذاتيًا ^{[ 10 ].}
• بادئات رموز العمليات المستخدمة في مجموعات تعليمات الحاسوب
• كمية متغيرة الطول

• بيرستل، جان؛ بيرين، دومينيك؛ رويتناور، كريستوف (2010). الشفرات والآلات . موسوعة الرياضيات وتطبيقاتها. المجلد  129. كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-88831-8. Zbl 1187.94001 . 
• إلياس، بيتر (1975). "مجموعات الكلمات المشفرة العالمية وتمثيلات الأعداد الصحيحة". مجلة IEEE للمعاملات في نظرية المعلومات . 21 (2): 194-203 . doi : 10.1109/tit.1975.1055349 . ISSN 0018-9448 . Zbl 0298.94011 .  
• DA Huffman، "طريقة لبناء رموز الحد الأدنى من التكرار"، وقائع IRE، سبتمبر 1952، ص  1098-1102 (مقالة Huffman الأصلية)
• نبذة تعريفية: ديفيد أ. هوفمان ، مجلة ساينتفك أمريكان ، سبتمبر 1991، الصفحات  54-58 (قصة خلفية)
• توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 16.3، الصفحات  385-392.
•  تتضمن هذه المقالة موادًا متاحة للعموم من المعيار الفيدرالي 1037C ، إدارة الخدمات العامة . مؤرشفة من الأصل بتاريخ 22 يناير 2022.

• الرموز والأشجار وخاصية البادئة بقلم كونا ماكفي