ترميز ثنائي مختصر

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

إذا كان n قوةً للعدد اثنين، فإن القيمة المشفرة لـ 0 ≤ x < n هي الشفرة الثنائية البسيطة لـ x بطول log ₂ ( n ). وإلا، فليكن k = floor(log ₂ ( n ))، بحيث يكون 2 ^k < n < 2 ^{k + 1} وليكن u = 2 ^{k + 1} − n .

يقوم التشفير الثنائي المقتطع بتعيين أول u رمزًا بطول k، ثم يقوم بتعيين آخر n − u رمزًا بطول k + 1 للرموز المتبقية . ولأن جميع الرموز بطول k + 1 تتكون من رمز غير معين بطول k مع إضافة "0" أو "1"، فإن الشفرة الناتجة هي شفرة بادئة .

تُستخدم رموز المرحلة الانتقالية منذ عام 1984 على الأقل، والمعروفة أيضًا باسم رموز الاقتصاد ، ^{[ 1 ] [ 2 ] [ 3 ]} وتُعرف أيضًا باسم التشفير الثنائي المقتطع.

على سبيل المثال، بالنسبة للأبجدية {0، 1، 2، 3، 4}، فإن n = 5 و 2 ² ≤ n < 2 ³ ، وبالتالي k = 2 و u = 2 ³ − 5 = 3. يقوم التشفير الثنائي المقتطع بتعيين أول u رمزًا للكلمات المشفرة 00 و 01 و 10، وكلها بطول 2، ثم يقوم بتعيين آخر n − u رمزًا للكلمات المشفرة 110 و 111، وهما آخر كلمتين مشفرتين بطول 3.

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

يتطلب الأمر 3 بتات لترميز n باستخدام الترميز الثنائي المباشر، وبالتالي فإن 2 ³ − n = 8 − 5 = 3 غير مستخدمة.

من الناحية العددية، لإرسال قيمة x ، حيث 0 ≤ x < n ، وحيث يوجد 2k ^≤ n < 2k ^{+ 1} رمزًا، يوجد u = ^{2k + 1} − n خانة غير مستخدمة عند تقريب حجم الأبجدية إلى أقرب قوة للعدد اثنين. وتتلخص عملية ترميز العدد x في النظام الثنائي المقتطع فيما يلي: إذا كانت x أقل من u ، يتم ترميزها في k بت ثنائي؛ وإذا كانت x أكبر من أو تساوي u ، يتم ترميز القيمة x + u في k + 1 بت ثنائي.

مثال آخر، يتطلب ترميز أبجدية بحجم 10 (بين 0 و9) 4  بتات، ولكن هناك 2 ^{^4} - 10 = 6 بتات غير مستخدمة، لذا يتم تجاهل البت الأول من قيم الإدخال الأقل من 6، بينما يتم إزاحة قيم الإدخال الأكبر من أو تساوي 6 بمقدار 6 إلى نهاية المساحة الثنائية. (الأنماط غير المستخدمة غير معروضة في هذا الجدول).

لفك التشفير، اقرأ أول k بت. إذا كانت القيمة المشفرة أقل من u ، فقد اكتمل فك التشفير. وإلا، اقرأ بتًا إضافيًا واطرح u من النتيجة.

إليك حالة أكثر تطرفًا: عندما يكون n = 7، فإن القوة التالية للعدد 2 هي 8، لذا فإن k = 2 و u = 2 ³ − 7 = 1:

يوضح هذا المثال الأخير أن بت الصفر البادئ لا يشير دائمًا إلى رمز قصير؛ إذا كان u < 2 ^k ، فإن بعض الرموز الطويلة ستبدأ ببت الصفر.

قم بإنشاء ترميز ثنائي مبتور لقيمة x ، 0 ≤ x < n ، حيث n > 0 هو حجم الأبجدية التي تحتوي على x . ليس بالضرورة أن يكون n قوة للعدد اثنين.

string TruncatedBinary ( int x , int n ) { // ضع k = floor(log2(n))، أي k بحيث يكون 2^k <= n < 2^(k+1). int k = 0 , t = n ; while ( t > 1 ) { k ++ ; t >>= 1 ; }// اضبط قيمة u على عدد الكلمات المشفرة غير المستخدمة = 2^(k+1) - n. int u = ( 1 << k + 1 ) - n ;إذا كان ( x < u ) أرجع Binary ( x , k )؛ وإلا أرجع Binary ( x + u , k + 1 ))؛ }

الروتين Binaryتوضيحي؛ عادةً ما يُراد فقط lenالبتات الموجودة في أقصى اليمين من المتغير x . هنا نقوم ببساطة بإخراج الشفرة الثنائية لـ x باستخدام lenالبتات، مع إضافة أصفار من الرتبة العليا إذا لزم الأمر.

دالة ` binary` تأخذ وسيطين : ` x` و` len` . تقوم الدالة بتكرار العملية على سلسلة نصية ثنائية ، حيث تُنشئ سلسلة نصية فارغة . ثم تُعيد السلسلة النصية `s` . طالما أن ` x` لا يساوي صفرًا ، تُضيف السلسلة النصية `s` إلى `0` ، وإلا تُضيفها إلى ` 1` . بعد ذلك ، تُكرر العملية على السلسلة النصية ` s` حتى يصبح طولها أقل من ` len` . ثم تُعيد السلسلة النصية ` s` .

إذا لم يكن n قوةً للعدد اثنين، وتمت ملاحظة الرموز المكونة من k بت باحتمالية p ، فسيتم ملاحظة الرموز المكونة من ( k + 1) بت باحتمالية 1 − p . يمكننا حساب العدد المتوقع للبتات لكل رمز.${\displaystyle b_{e}}$مثل

${\displaystyle b_{e}=pk+(1-p)(k+1).}$

يحتوي الترميز الخام للرمز على${\displaystyle b_{u}=k+1}$بتات. ثم يمكن تعريف توفير المساحة النسبية (انظر نسبة ضغط البيانات ) للترميز على النحو التالي:

${\displaystyle s=1-{\frac {b_{e}}{b_{u}}}=1-{\frac {pk+(1-p)(k+1)}{k+1}}.}$

عند تبسيط هذا التعبير، فإنه يؤدي إلى

${\displaystyle s={\frac {p}{k+1}}={\frac {p}{b_{u}}}.}$

يشير هذا إلى أن الكفاءة النسبية للترميز الثنائي المقتطع تزداد مع ازدياد احتمالية p للرموز ذات k بت، وطول بت رمز الترميز الخام${\displaystyle b_{u}}$يتناقص.

• قانون بنفورد
• ترميز غولومب