رمز البادئة

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

على سبيل المثال، رمز مع رمز${\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 .

The variable-length Huffman codes, telephone country codes, the country and publisher parts of ISBNs, the Secondary Synchronization Codes used in the UMTSW-CDMA 3G Wireless Standard, and the instruction sets (machine language) of most computer microarchitectures are prefix codes.

Prefix codes are not error-correcting codes. In practice, a message might first be compressed with a prefix code, and then encoded again with channel coding (including error correction) before transmission.

For every uniquely decodable code there is a prefix code that has the same code word lengths.^[5]Kraft's inequality characterizes the sets of code word lengths that are possible in a uniquely decodable code.^[6]

If every word in the code has the same length, the code is called a fixed-length code, or a block code (though the term block code is also used for fixed-size error-correcting codes in channel coding). For example, ISO 8859-15 letters are always 8 bits long. UTF-32/UCS-4 letters are always 32 bits long. ATM cells are always 424 bits (53 bytes) long. A fixed-length code of fixed length ${\displaystyle k}$ bits can encode up to ${\displaystyle 2^{k}}$ source symbols.

A fixed-length code is necessarily a prefix code. It is possible to turn any code into a fixed-length code by padding fixed symbols to the shorter prefixes in order to meet the length of the longest prefixes. Alternately, such padding codes may be employed to introduce redundancy that allows autocorrection and/or synchronisation. However, fixed length encodings are inefficient in situations where some words are much more likely to be transmitted than others.

Truncated binary encoding is a straightforward generalization of fixed-length codes to deal with cases where the number of symbols n is not a power of two. Source symbols are assigned codewords of length ${\displaystyle k}$ and ${\displaystyle k+1}$, where ${\displaystyle k}$ is chosen so that ${\displaystyle 2^{k}<n\leq 2^{k+1}}$.

Huffman coding is a more sophisticated technique for constructing variable-length prefix codes. The Huffman coding algorithm takes as input the frequencies that the code words should have, and constructs a prefix code that minimizes the weighted average of the code word lengths. (This is closely related to minimizing the entropy.) This is a form of lossless data compression based on entropy encoding.

تستخدم بعض الشفرات رمزًا خاصًا يُسمى "الفاصلة" (يُعرف أيضًا بالقيمة المرجعية )، وهو يختلف عن البيانات العادية. ^{[ 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.

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