الترميز الحسابي

الترميز الحسابي ( AC ) هو شكل من أشكال ترميز الإنتروبيا يُستخدم في ضغط البيانات بدون فقدان . عادةً، تُمثَّل سلسلة الأحرف باستخدام عدد ثابت من البتات لكل حرف، كما هو الحال في ترميز ASCII . عند تحويل سلسلة إلى ترميز حسابي، تُخزَّن الأحرف شائعة الاستخدام بعدد أقل من البتات، بينما تُخزَّن الأحرف الأقل استخدامًا بعدد أكبر من البتات، مما يؤدي إلى استخدام عدد أقل من البتات إجمالًا. يختلف الترميز الحسابي عن أشكال ترميز الإنتروبيا الأخرى، مثل ترميز هوفمان ، في أنه بدلًا من فصل المدخلات إلى رموز مكونة واستبدال كل منها برمز، يقوم الترميز الحسابي بترميز الرسالة بأكملها إلى رقم واحد، وهو كسر ذو دقة اختيارية q ، حيث 0.0 ≤ q < 1.0 . ^{[ 1 ]}

العلاقة بالإنتروبيا

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

عندما تكون جميع الرموز متساوية الاحتمالية، يكون لكل فترة فرعية نفس الحجم، ولا يمكن تمثيل أي رمز بعدد بتات أقل من أي رمز آخر. في هذه الحالة، تصل الإنتروبيا إلى أقصى قيمة لها. $\log _{2}n$ بت لكل رمز (حيث $n$ (حيث يمثل حجم الأبجدية)، ولا يمكن ضغطها. على سبيل المثال، يبلغ إنتروبيا سلسلة من رميات عملة معدنية مستقلة وعادلة بتًا واحدًا بالضبط لكل رمز - وهو ما يعادل تكلفة التخزين بالكامل - لذا فإن الترميز الحسابي لا يُقدم أي فائدة. وبالمثل، فإن الرموز الثلاثية المستقلة ذات الاحتمالات المتساوية لها إنتروبيا تبلغ حوالي 1.585 بت لكل رمز، وهي القيمة القصوى لأبجدية مكونة من ثلاثة رموز، وهي غير قابلة للضغط أيضًا. ^{[ 3 ]}^{[ 2 ]}

يصبح الضغط ممكنًا عندما تكون الاحتمالات غير متساوية، لأن الفترات الفرعية تصبح غير متساوية في الحجم. على سبيل المثال، مصدر ثنائي باحتمالات 0.9 و0.1 لديه إنتروبيا تقارب 0.469 بت لكل رمز. يستقبل الرمز ذو الاحتمال 0.9 نسبة 90% من كل فترة، لذا فإن معظم خطوات التشفير لا تُقلّص الفترة إلا قليلًا، ويقل عدد البتات اللازمة لتحديد القيمة النهائية. هذا يسمح للترميز الحسابي بتحقيق نسبة ضغط تقارب 2.1:1. ^{[ 3 ]}^{[ 1 ]}

تفاصيل التنفيذ وأمثلة

احتمالات متساوية

في أبسط الحالات، يكون احتمال ظهور كل رمز متساوياً. على سبيل المثال، لنفترض مجموعة من ثلاثة رموز، A وB وC، لكل منها احتمال ظهور متساوٍ. يتطلب ترميز الرموز واحداً تلو الآخر استخدام بتين لكل رمز، وهو أمر غير مُجدٍ: إذ لا يُستخدم أحد متغيرات البتات. بمعنى آخر، يمكن ترميز الرموز A وB وC على التوالي كـ 00 و01 و10، مع بقاء البت 11 غير مُستخدم. ^{[ 1 ]}

الحل الأكثر كفاءة هو تمثيل سلسلة هذه الرموز الثلاثة كعدد نسبي في النظام الثلاثي، حيث يمثل كل رقم رمزًا. على سبيل المثال، يمكن تحويل السلسلة "ABBCAB" إلى 0.011201 ₍ في الترميز الحسابي) كقيمة في الفترة [ 0، 1). الخطوة التالية هي ترميز هذا العدد الثلاثي باستخدام عدد ثنائي ذي فاصلة ثابتة بدقة كافية لاستعادته، مثل 0.0010110001 ₍ هذا العدد يتكون من 10 بتات فقط؛ أي توفير بتين مقارنةً بالترميز الكتلي البسيط). هذا ممكن للسلاسل الطويلة لوجود خوارزميات فعالة ومُطبقة في مكانها لتحويل أساس الأعداد ذات الدقة العالية. ^{[ 5 ]}

لفك تشفير القيمة، بمعرفة أن السلسلة الأصلية كان طولها 6، يمكن للمرء ببساطة التحويل مرة أخرى إلى الأساس 3، والتقريب إلى 6 أرقام، واستعادة السلسلة.

تحديد نموذج

بشكل عام، يمكن لخوارزميات الترميز الحسابي إنتاج مخرجات شبه مثالية لأي مجموعة معينة من الرموز والاحتمالات. (القيمة المثلى هي −log ₂P بت لكل رمز باحتمال P ؛ انظر نظرية ترميز المصدر ). ^{[ 2 ]} تبدأ خوارزميات الضغط التي تستخدم الترميز الحسابي بتحديد نموذج للبيانات - وهو في الأساس تنبؤ بالأنماط التي سيتم العثور عليها في رموز الرسالة. كلما كان هذا التنبؤ أكثر دقة، كانت المخرجات أقرب إلى المستوى الأمثل. ^{[ 1 ]}

مثال : قد يكون النموذج البسيط والثابت لوصف مخرجات جهاز مراقبة معين بمرور الوقت كما يلي:

احتمال ظهور الرمز محايد بنسبة 60%
احتمال ظهور الرمز إيجابي 20%
احتمال ظهور الرمز السلبي 10%
احتمال ظهور رمز نهاية البيانات هو 10%. (يشير وجود هذا الرمز إلى أن التدفق سيتم "إنهاؤه داخليًا"، وهو أمر شائع إلى حد ما في ضغط البيانات؛ عندما يظهر هذا الرمز في تدفق البيانات، سيعرف جهاز فك التشفير أن التدفق بأكمله قد تم فك تشفيره.)

يمكن للنماذج أيضًا التعامل مع أبجديات أخرى غير مجموعة الرموز الأربعة البسيطة المختارة لهذا المثال. كما توجد نماذج أكثر تعقيدًا: إذ تُغير النماذج ذات الرتبة الأعلى تقديرها للاحتمالية الحالية لرمز ما بناءً على الرموز التي تسبقه ( السياق )، بحيث يكون احتمال ظهور الحرف "u" في نموذج للنص الإنجليزي، على سبيل المثال، أعلى بكثير عندما يليه الحرف "Q" أو "q". بل يمكن للنماذج أن تكون تكيفية ، بحيث تُغير باستمرار توقعاتها للبيانات بناءً على محتوى التدفق الفعلي. يجب أن يكون لدى المُفكِّك نفس نموذج المُشفِّر. ^{[ 1 ]}^{[ 6 ]}

التشفير وفك التشفير: نظرة عامة

بشكل عام، كل خطوة من خطوات عملية التشفير، باستثناء الأخيرة، هي نفسها؛ لدى المشفر أساسًا ثلاثة أجزاء فقط من البيانات للنظر فيها: ^{[ 1 ]}

الرمز التالي الذي يجب ترميزه
الفاصل الزمني الحالي (في بداية عملية التشفير، يتم ضبط الفاصل الزمني على [0,1] ، ولكن هذا سيتغير)
الاحتمالات التي يخصصها النموذج لكل رمز من الرموز المختلفة الممكنة في هذه المرحلة (كما ذكرنا سابقًا، فإن النماذج ذات الرتبة الأعلى أو النماذج التكيفية تعني أن هذه الاحتمالات ليست بالضرورة هي نفسها في كل خطوة).

يقسم المُشفِّر الفترة الحالية إلى فترات فرعية، تمثل كل منها جزءًا من الفترة الحالية يتناسب مع احتمالية ظهور ذلك الرمز في السياق الحالي. وتصبح الفترة التي تتوافق مع الرمز الفعلي المراد تشفيره هي الفترة المستخدمة في الخطوة التالية. ^{[ 1 ]}

مثال : بالنسبة للنموذج ذي الرموز الأربعة أعلاه:

ستكون الفترة الزمنية للحالة المحايدة [0، 0.6)
ستكون الفترة الزمنية للقيمة الموجبة [0.6، 0.8)
ستكون الفترة الزمنية للقيمة السالبة [0.8، 0.9)
ستكون الفترة الزمنية لنهاية البيانات [0.9، 1) .

بعد ترميز جميع الرموز، تحدد الفترة الناتجة بشكل قاطع تسلسل الرموز التي أنتجتها. ويمكن لأي شخص يمتلك نفس الفترة النهائية والنموذج المستخدم إعادة بناء تسلسل الرموز الذي دخل إلى جهاز الترميز لينتج عنه تلك الفترة النهائية. ^{[ 1 ]}

ليس من الضروري إرسال الفاصل الزمني الأخير، بل يكفي إرسال كسر واحد يقع ضمن هذا الفاصل. وبالتحديد، يكفي إرسال عدد كافٍ من أرقام الكسر (بأي أساس كان) بحيث تقع جميع الكسور التي تبدأ بتلك الأرقام ضمن الفاصل الزمني الأخير؛ وهذا يضمن أن يكون الرمز الناتج رمزًا بادئًا . ^{[ 7 ]}

التشفير وفك التشفير: مثال

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

تبدأ العملية بنفس الفترة الزمنية التي يستخدمها المُشفِّر: [0,1) ، وباستخدام النموذج نفسه، يتم تقسيمها إلى نفس الفترات الفرعية الأربع التي يجب أن يمتلكها المُشفِّر. يقع الكسر 0.538 ضمن الفترة الفرعية للرمز المحايد، [0, 0.6) ؛ وهذا يشير إلى أن أول رمز قرأه المُشفِّر كان الرمز المحايد، وبالتالي فهو أول رمز في الرسالة.

ثم قسّم الفترة [0، 0.6) إلى فترات فرعية:

ستكون الفترة الزمنية للمحايد [0، 0.36) ، 60% من [0، 0.6) .
ستكون الفترة الزمنية للقيمة الإيجابية [0.36، 0.48) ، 20% من [0، 0.6) .
ستكون الفترة الزمنية للقيمة السالبة [0.48، 0.54) ، 10% من [0، 0.6) .
ستكون الفترة الزمنية لنهاية البيانات [0.54، 0.6) ، 10% من [0، 0.6) .

بما أن 0.538 يقع ضمن الفترة [0.48، 0.54) ، فإن الرمز الثاني للرسالة يجب أن يكون سلبياً.

قم بتقسيم الفترة الحالية مرة أخرى إلى فترات فرعية:

ستكون الفترة الزمنية للمحايد [0.48، 0.516) .
ستكون الفترة الزمنية للقيمة الإيجابية [0.516، 0.528) .
ستكون الفترة الزمنية للقيمة السالبة [0.528، 0.534) .
ستكون الفترة الزمنية لنهاية البيانات [0.534، 0.540) .

يقع الرقم 0.538 الآن ضمن نطاق رمز نهاية البيانات؛ لذا، يجب أن يكون هذا هو الرمز التالي. وبما أنه رمز الإنهاء الداخلي أيضًا، فهذا يعني اكتمال عملية فك التشفير. إذا لم يتم إنهاء التدفق داخليًا، فلا بد من وجود طريقة أخرى للإشارة إلى نقطة توقفه. وإلا، فقد تستمر عملية فك التشفير إلى ما لا نهاية، مما يؤدي إلى قراءة رموز من الكسر أكثر مما تم ترميزه فيه فعليًا. ^{[ 1 ]}

مصادر عدم الكفاءة

كان من الممكن ترميز الرسالة 0.538 في المثال السابق باستخدام الكسور القصيرة المتساوية 0.534، 0.535، 0.536، 0.537، أو 0.539. يشير هذا إلى أن استخدام النظام العشري بدلًا من النظام الثنائي قد أدى إلى بعض أوجه القصور. وهذا صحيح؛ فمحتوى المعلومات في عدد عشري مكون من ثلاثة أرقام هو $3\times \log _{2}(10)\approx 9.966$ بتات ؛ كان من الممكن ترميز الرسالة نفسها في الكسر الثنائي 0.10001001 (المكافئ لـ 0.53515625 بالنظام العشري) بتكلفة 8 بتات فقط. ^{[ 7 ]}

هذا الناتج ذو 8 بتات أكبر من محتوى المعلومات، أو الإنتروبيا ، للرسالة، وهو

\sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ بت}}.

لكن يجب استخدام عدد صحيح من البتات في التشفير الثنائي، لذا سيستخدم مُشفِّر هذه الرسالة 8 بتات على الأقل، مما ينتج عنه رسالة أكبر بنسبة 8.4% من محتوى الإنتروبيا. هذا النقص في الكفاءة، الذي لا يتجاوز بتًا واحدًا، يُقلل من الحمل الزائد نسبيًا مع ازدياد حجم الرسالة. ^{[ 7 ]}

علاوة على ذلك، كانت احتمالات الرموز المُعلنة [0.6، 0.2، 0.1، 0.1] ، بينما الترددات الفعلية في هذا المثال هي [0.33، 0، 0.33، 0.33] . إذا أُعيد ضبط الفترات الزمنية لهذه الترددات، فإن إنتروبيا الرسالة ستكون 4.755 بت، ويمكن ترميز رسالة NEUTRAL NEGATIVE END-OF-DATA نفسها كفترات زمنية [0، 1/3]؛ [1/9، 2/9]؛ [5/27، 6/27]؛ وفترة ثنائية [0.00101111011، 0.00111000111] . يُعد هذا أيضًا مثالًا على كيفية إنتاج أساليب الترميز الإحصائي، مثل الترميز الحسابي، رسالة إخراج أكبر من رسالة الإدخال، خاصةً إذا كان نموذج الاحتمالية غير دقيق. ^{[ 1 ]}

الترميز الحسابي التكيفي

إحدى مزايا الترميز الحسابي مقارنةً بأساليب ضغط البيانات الأخرى المماثلة هي سهولة التكيف. التكيف هو تغيير جداول التكرار (أو الاحتمالية) أثناء معالجة البيانات. تتطابق البيانات المُفكَّكة مع البيانات الأصلية طالما تم استبدال جدول التكرار في عملية فك التشفير بنفس الطريقة وفي نفس الخطوة كما في عملية التشفير. يعتمد التزامن عادةً على مجموعة من الرموز التي تظهر أثناء عمليتي التشفير وفك التشفير. ^{[ 1 ]}^{[ 6 ]}

الدقة وإعادة التطبيع

تتضمن الشروحات السابقة للترميز الحسابي بعض التبسيط. على وجه الخصوص، كُتبت كما لو أن المُشفِّر قام أولاً بحساب الكسور التي تُمثل نهايتي الفترة بالكامل، باستخدام دقة لا نهائية ، ثم حوّل الكسر إلى شكله النهائي في نهاية عملية الترميز. بدلاً من محاولة محاكاة الدقة اللانهائية، تعمل معظم برامج الترميز الحسابي عند حد ثابت للدقة، مع العلم أن المُفكِّك سيتمكن من مُطابقته، وتُقرِّب الكسور المحسوبة إلى أقرب ما يُعادلها عند تلك الدقة. ^{[ 7 ]} يُوضح مثال كيف سيعمل هذا إذا تطلّب النموذج تقسيم الفترة $[0,1)$ إلى ثلاثة أجزاء، وتم تقريب ذلك بدقة 8 بت. لاحظ أنه بما أن الدقة معروفة الآن، فإن نطاقات الأرقام الثنائية التي سنتمكن من استخدامها معروفة أيضاً.

رمز	احتمال	تم تقليل الفاصل الزمني إلى دقة ثمانية بت		يتراوح
رمز	(معبر عنها ككسر)	(على شكل كسور)	(بالنظام الثنائي)	(بالنظام الثنائي)
أ	1/3	$[0, 85/256)$	[0.00000000, 0.01010101)	00000000 – 01010100
ب	1/3	$[85/256, 171/256]$	[0.01010101, 0.10101011)	01010101 – 10101010
ج	1/3	$[171/256، 1)$	[0.10101011, 1.00000000)	10101011 – 11111111

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

رمز	احتمال	يتراوح	الأرقام التي يمكن إرسالها إلى المخرج	المدى بعد إعادة التطبيع
أ	1/3	0 0000000 – 0 1010100	0	0000000 0 – 1010100 1
ب	1/3	01010101 – 10101010	لا أحد	01010101 – 10101010
ج	1/3	1 0101011 – 1 1111111	1	0101011 0 – 1111111 1

الترميز الحسابي كتغيير معمّم للأساس

تذكر أنه في حالة تساوي احتمالات الرموز، يمكن تطبيق الترميز الحسابي بتغيير بسيط في الأساس. وبشكل عام، يمكن تفسير الترميز الحسابي (وترميز النطاق) على أنه تغيير معمّم في الأساس . ^[⁵^] على سبيل المثال، يمكننا النظر إلى أي سلسلة من الرموز :

\mathrm {DABDDB}

كرقم في أساس معين، بافتراض أن الرموز المستخدمة تشكل مجموعة مرتبة، وأن كل رمز في هذه المجموعة يمثل عددًا صحيحًا متسلسلًا (A = 0، B = 1، C = 2، D = 3، وهكذا). ينتج عن ذلك التكرارات والتكرارات التراكمية التالية:

رمز	تكرار الحدوث	التكرار التراكمي
أ	1	0
ب	2	1
د	3	3

التكرار التراكمي لعنصر ما هو مجموع جميع التكرارات التي تسبق ذلك العنصر. بعبارة أخرى، التكرار التراكمي هو مجموع تراكمي للتكرارات.

في نظام العد الموضعي ، يُساوي الأساس عدديًا عددًا من الرموز المختلفة المستخدمة للتعبير عن العدد. على سبيل المثال، في النظام العشري، يبلغ عدد الرموز 10، وهي: 0، 1، 2، 3، 4، 5، 6، 7، 8، و9. يُستخدم الأساس للتعبير عن أي عدد صحيح محدود بمضاعف مُفترض في صورة متعددة الحدود. على سبيل المثال، العدد 457 هو في الواقع 4 × 10² ⁺ 5 × ^10¹ + 7 × ^10⁰ ، حيث يُفترض الأساس 10 ولكنه غير مُوضح صراحةً.

سنقوم في البداية بتحويل DABDDB إلى عدد سداسي، لأن طول السلسلة هو 6. يتم أولاً تحويل السلسلة إلى سلسلة الأرقام 301331، والتي بدورها تُحوّل إلى عدد صحيح باستخدام متعددة الحدود التالية:

6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^{0}\times 1=23671

يبلغ طول النتيجة 23671 15 بت، وهو ليس قريبًا جدًا من الحد النظري ( إنتروبيا الرسالة)، والذي يبلغ حوالي 9 بت. ^{[ 3 ]}

لترميز رسالة بطول أقرب إلى الحد النظري الذي تفرضه نظرية المعلومات، نحتاج إلى تعميم الصيغة الكلاسيكية لتغيير الأساس قليلاً. سنحسب الحدين الأدنى والأعلى L و U ، ثم نختار قيمة بينهما. لحساب L، نضرب كل حد في التعبير أعلاه في حاصل ضرب ترددات جميع الرموز التي ظهرت سابقًا: ^{[ 5 ]}

{\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{0}\times 1){}\\={}&25002\end{aligned}}

الفرق بين هذه المعادلة متعددة الحدود والمعادلة متعددة الحدود أعلاه هو أن كل حد يُضرب في حاصل ضرب ترددات جميع الرموز التي ظهرت سابقًا. وبشكل أعم، يمكن حساب L على النحو التالي:

L=\sum _{i=1}^{n}n^{ni}C_{i}{\prod _{k=1}^{i-1}f_{k}}

أين $\scriptstyle C_{i}$ هي الترددات التراكمية و $\scriptstyle f_{k}$ تمثل هذه القيم ترددات الظهور. وتشير المؤشرات إلى موضع الرمز في الرسالة. في الحالة الخاصة التي تكون فيها جميع الترددات $\scriptstyle f_{k}$ إذا كانت القيمة 1، فهذه هي صيغة تغيير الأساس. ^{[ 5 ]}

الحد الأعلى U يساوي L زائد حاصل ضرب جميع الترددات؛ في هذه الحالة U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. بشكل عام، يُعطى U بالصيغة التالية:

U=L+\prod _{k=1}^{n}f_{k}

يمكننا الآن اختيار أي عدد من الفترة [ L , U ) لتمثيل الرسالة؛ ومن الخيارات المناسبة القيمة التي تحتوي على أطول سلسلة أصفار ممكنة، وهي 25100، لأنها تسمح لنا بتحقيق الضغط من خلال تمثيل النتيجة على أنها 251 × 10² ^. ويمكن أيضًا اقتطاع الأصفار، ليصبح الناتج 251، إذا تم تخزين طول الرسالة بشكل منفصل. تميل الرسائل الأطول إلى امتلاك سلاسل أصفار أطول.

لفك تشفير العدد الصحيح 25100، يمكن عكس عملية حساب كثير الحدود كما هو موضح في الجدول أدناه. في كل مرحلة، يتم تحديد الرمز الحالي، ثم يُطرح الحد المقابل من النتيجة.

الباقي	تعريف	تم تحديد الرمز	الباقي المصحح
25100	25100 / 6 ⁵ = 3	د	(25100 − 6 ⁵ × 3) / 3 = 590
590	590 / 6 ⁴ = 0	أ	(590 − 6 ⁴ × 0) / 1 = 590
590	590 / 6 ³ = 2	ب	(590 − 6 ³ × 1) / 2 = 187
187	187 / 6 ² = 5	د	(187 − 6 ² × 3) / 3 = 26
26	26 / 6 ¹ = 4	د	(26 − 6 ¹ × 3) / 3 = 2
2	2 / 6 ⁰ = 2	ب	—

أثناء فك التشفير، نأخذ الجزء الصحيح بعد القسمة على القوة المناسبة للعدد 6. ثم تُقارن النتيجة بالفترات التراكمية، ويُختار الرمز المناسب من جدول البحث. عند تحديد الرمز، تُصحح النتيجة. تستمر العملية طوال طول الرسالة المعروف أو طالما أن النتيجة المتبقية موجبة. الفرق الوحيد مقارنةً بتغيير الأساس التقليدي هو أنه قد يكون هناك نطاق من القيم المرتبطة بكل رمز. في هذا المثال، A دائمًا 0، وB إما 1 أو 2، وD أي من 3 أو 4 أو 5. يتوافق هذا تمامًا مع فتراتنا المحددة بالترددات. عندما تكون جميع الفترات مساوية لـ 1، فإننا أمام حالة خاصة من تغيير الأساس التقليدي. ^{[ 5 ]}

الحد النظري للرسالة المضغوطة

لا يتجاوز الحد الأدنى L أبدًا n ⁿ ، حيث n هو حجم الرسالة، وبالتالي يمكن تمثيله في $\log _{2}(n^{n})=n\log _{2}(n)$ بتات. بعد حساب الحد الأعلى U واختزال الرسالة باختيار رقم من الفترة [ L , U ) ذي أطول سلسلة من الأصفار، يمكننا أن نفترض أن هذا الطول يمكن تقليله بواسطة $\textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)$ البتات. بما أن كل تردد في الناتج يتكرر بنفس عدد مرات قيمة هذا التردد، يمكننا استخدام حجم الأبجدية A لحساب الناتج.

\prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.

بتطبيق log ₂ على العدد المقدر للبتات في الرسالة، فإن الرسالة النهائية (دون احتساب الحمل الزائد اللوغاريتمي لجداول طول الرسالة والتردد) ستتطابق مع عدد البتات الذي تحدده الإنتروبيا ، وهو بالنسبة للرسائل الطويلة قريب جدًا من العدد الأمثل: ^{[ 3 ]}^{[ 2 ]}

-\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH

بمعنى آخر، تقترب كفاءة الترميز الحسابي من الحد النظري لـ $H$ عدد البتات لكل رمز، حيث يقترب طول الرسالة من اللانهاية.

التوزيع المتساوي المقارب

يمكننا فهم هذا بديهيًا. لنفترض أن المصدر إرجودي، فإنه يتمتع بخاصية التوزيع المتساوي التقاربي (AEP). وبحسب خاصية التوزيع المتساوي التقاربي، بعد تدفق طويل من $n$ الرموز، فاصل $(0,1)$ ^[³^] يتم تقسيمها تقريبًا إلى فترات متساوية الحجم تقريبًا.

من الناحية الفنية، بالنسبة لأي شيء صغير $\epsilon >0$ ، لجميع الأحجام الكبيرة بما فيه الكفاية $n$ ، يوجد $2^{nH(X)(1+O(\epsilon ))}$ السلاسل $x_{1:n}$ بحيث يكون لكل سلسلة احتمال متساوٍ تقريبًا $Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}$ واحتمالها الإجمالي هو $1-O(\epsilon )$ .

بالنسبة لأي سلسلة من هذا القبيل، يتم ترميزها حسابيًا بواسطة سلسلة ثنائية بطول $k$ ، أين $k$ هو الأصغر $k$ بحيث يوجد جزء من الشكل ${\frac {?}{2^{k}}}$ في الفترة الزمنية لـ $x_{1:n}$ بما أن الفترة الزمنية لـ $x_{1:n}$ له حجم $2^{-nH(X)(1+O(\epsilon ))}$ ، ينبغي أن نتوقع أن يحتوي على جزء واحد من الشكل ${\frac {?}{2^{k}}}$ متى $k=nH(X)(1+O(\epsilon ))$ .

وبالتالي، باحتمالية عالية، $x_{1:n}$ يمكن ترميزها حسابيًا بسلسلة ثنائية طولها $nH(X)(1+O(\epsilon ))$ [ ³^]

الاتصالات مع طرق الضغط الأخرى

ترميز هوفمان

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

عند استخدام ترميز هوفمان البسيط للسلاسل الثنائية، لا يمكن تحقيق أي ضغط، حتى مع انخفاض الإنتروبيا (على سبيل المثال، احتمالات ({0, 1}) هي {0.95, 0.05}). يخصص ترميز هوفمان بتًا واحدًا لكل قيمة، مما ينتج عنه رمز بنفس طول المدخلات. في المقابل، يضغط الترميز الحسابي البتات بشكل جيد، مقتربًا من نسبة الضغط المثلى المذكورة في المرجع ^{[ 7 ].}

1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.

إحدى الطرق البسيطة لمعالجة عدم كفاءة ترميز هوفمان هي دمج الرموز ("الحجب") لتشكيل أبجدية جديدة، حيث يمثل كل رمز جديد سلسلة من الرموز الأصلية - في هذه الحالة بتات - من الأبجدية الأصلية. في المثال أعلاه، سيؤدي تجميع سلاسل من ثلاثة رموز قبل الترميز إلى إنتاج "رموز فائقة" جديدة بالترددات التالية: ^{[ 6 ]}

٠٠٠85.7%
001،010،1004.5% لكل منها
011،101،110: 0.24% لكل منها
1110.0125%

مع هذا التجميع، يبلغ متوسط ترميز هوفمان 1.3 بت لكل ثلاثة رموز، أو 0.433 بت لكل رمز، مقارنةً ببت واحد لكل رمز في الترميز الأصلي، أي $56.7\%$ الضغط. إن السماح بتسلسلات كبيرة بشكل تعسفي يقترب بشكل تعسفي من الإنتروبيا - تمامًا مثل الترميز الحسابي - ولكنه يتطلب رموزًا ضخمة للقيام بذلك، لذا فهو ليس عمليًا مثل الترميز الحسابي لهذا الغرض. ^{[ 6 ]}

يُعدّ ترميز أطوال التشغيل باستخدام رموز غولومب-رايس القائمة على خوارزمية هوفمان بديلاً آخر . يتيح هذا النهج ترميزًا/فك ترميز أبسط وأسرع من الترميز الحسابي أو حتى ترميز هوفمان، نظرًا لأن الأخير يتطلب البحث في جداول. في المثال {0.95، 0.05}، يحقق رمز غولومب-رايس مع باقي قسمة من أربعة بتات نسبة ضغط تبلغ $71.1\%$ وهي أقرب بكثير إلى الحل الأمثل من استخدام كتل ثلاثية البتات. ومع ذلك، فإن رموز غولومب-رايس لا تنطبق إلا على مدخلات برنولي مثل تلك الموجودة في هذا المثال، لذا فهي ليست بديلاً عن التجزئة في جميع الحالات. ^{[ 6 ]}

التاريخ وبراءات الاختراع

طُوِّرت الخوارزميات الأساسية للترميز الحسابي بشكل مستقل من قبل جورما ج. ريسانين ، في قسم الأبحاث بشركة آي بي إم ، ومن قبل ريتشارد سي. باسكو، طالب الدكتوراه في جامعة ستانفورد ؛ ونُشرت كلتاهما في مايو 1976. ^{[ 5 ]}^{[ 9 ]} ويستشهد باسكو بمسودة ما قبل النشر لمقال ريسانين ويعلق على العلاقة بين أعمالهما: ^{[ 9 ]}

طُوِّرت إحدى خوارزميات هذه العائلة بشكل مستقل بواسطة ريسانين [1976]. تقوم هذه الخوارزمية بنقل عنصر الكود إلى الطرف الأكثر أهمية من المُراكم، باستخدام مؤشر مُستخلص من الجمع والرفع الأسي. سنقارن الآن البدائل في الخيارات الثلاثة، وسنرى أنه من الأفضل نقل عنصر الكود بدلاً من المُراكم، وإضافة عناصر الكود إلى الطرف الأقل أهمية من المُراكم.

بعد أقل من عام على نشر العمل، تقدمت شركة IBM بطلب للحصول على براءة اختراع أمريكية لعمل ريسانين. أما عمل باسكو فلم يحصل على براءة اختراع.

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

على الأقل، توقف برنامج ضغط البيانات الشهير bzip2 عن استخدام الترميز الحسابي لصالح ترميز هوفمان، وذلك بسبب مخاوف تتعلق ببراءات الاختراع آنذاك. كذلك، فإن برامج ترميز وفك ترميز ملفات JPEG ، التي تدعم كلا الترميزين الحسابي وهوفمان، لا تدعم عادةً إلا ترميز هوفمان، وهو ما كان في الأصل بسبب مخاوف تتعلق ببراءات الاختراع. ونتيجةً لذلك، تستخدم جميع صور JPEG المستخدمة اليوم تقريبًا ترميز هوفمان ^{[ 10 ]،} على الرغم من انتهاء صلاحية براءات اختراع الترميز الحسابي لـ JPEG ^{[ 11 ]} نظرًا لقدم معيار JPEG (الذي اكتمل تصميمه تقريبًا بحلول عام 1990). ^{[ 12 ]} JPEG XL ، بالإضافة إلى برامج الأرشفة مثل PackJPG و Brunsli و Lepton ، التي يمكنها تحويل ملفات Huffman المشفرة بدون فقدان إلى ملفات ذات ترميز حسابي (أو أنظمة عددية غير متماثلة في حالة JPEG XL)، تُظهر توفيرًا في الحجم يصل إلى 25٪.

تعتمد خوارزمية الترميز الحسابي لتنسيق ضغط الصور JPEG على براءات الاختراع المذكورة أدناه (التي انتهت صلاحيتها). ^{[ 13 ]}

براءة الاختراع الأمريكية رقم 4,652,856 - ( IBM ) تم تقديمها في 4 فبراير 1986، وتم منحها في 24 مارس 1987 - Kottappuram MA Mohiuddin, Jorma Johannes Rissanen - كود حسابي متعدد الحروف الهجائية خالي من الضرب
براءة اختراع أمريكية رقم 4,905,297 – (شركة آي بي إم) تاريخ الإيداع 18 نوفمبر 1988، تاريخ المنح 27 فبراير 1990 – جلين جورج لانغدون، جوان إل. ميتشل، ويليام بي. بينيباكر، يورما يوهانس ريسانين – نظام ترميز وفك ترميز حسابي
براءة اختراع أمريكية رقم 4,935,882 – (شركة آي بي إم) تاريخ الإيداع: 20 يوليو 1988، تاريخ المنح: 19 يونيو 1990 – ويليام ب. بينيباكر، جوان ل. ميتشل – تكييف الاحتمالات لمبرمجي العمليات الحسابية
براءة اختراع جي بي رقم 1021672 - ( ميتسوبيشي ) تم تقديمها في 21 يناير 1989، ومنحت في 10 أغسطس 1990 - توشيهيرو كيمورا، شيجينوري كينو، فوميتاكا أونو، ماسايوكي يوشيدا - نظام الترميز
براءة اختراع جي بي رقم 2-46275 - (ميتسوبيشي) تم تقديمها في 26 فبراير 1990، ومنحت في 5 نوفمبر 1991 - فوميتاكا أونو، توموهيرو كيمورا، ماسايوكي يوشيدا، شيغينوري كينو - جهاز الترميز وطريقة الترميز

تشمل براءات الاختراع الأخرى (معظمها منتهية الصلاحية أيضًا) المتعلقة بالترميز الحسابي ما يلي.

براءة اختراع أمريكية رقم 4,122,440 – (شركة آي بي إم) تاريخ الإيداع: 4 مارس 1977، تاريخ المنح: 24 أكتوبر 1978 – غلين جورج لانغدون، يورما يوهانس ريسانين – طريقة ووسائل لترميز السلاسل الحسابية
براءة اختراع أمريكية رقم 4,286,256 – (شركة آي بي إم) تاريخ الإيداع 28 نوفمبر 1979، تاريخ المنح 25 أغسطس 1981 – جلين جورج لانغدون، يورما يوهانس ريسانين – طريقة ووسائل للترميز الحسابي باستخدام عدد أقل من العمليات
براءة اختراع أمريكية رقم 4,467,317 – (شركة آي بي إم) تاريخ الإيداع: 30 مارس 1981، تاريخ المنح: 21 أغسطس 1984 – غلين جورج لانغدون، يورما يوهانس ريسانين – ترميز ضغط حسابي عالي السرعة باستخدام تحديث القيمة المتزامن
براءة اختراع أمريكية رقم 4,891,643 – (شركة آي بي إم) تاريخ الإيداع 15 سبتمبر 1986، تاريخ المنح 2 يناير 1990 – جوان إل. ميتشل، ويليام بي. بينيباكر – ضغط/فك ضغط بيانات الترميز الحسابي باستخدام مُشفِّرات ومفكِّكات ترميز حسابي متنوعة ومُختارة بعناية.
براءة اختراع يابانية رقم 11782787 – ( NEC ) مُقدمة بتاريخ 13 مايو 1987، مُنحت بتاريخ 18 نوفمبر 1988 – ميتشيو شيمادا – جهاز ترميز حسابي لضغط البيانات
براءة اختراع يابانية رقم 15015487 – ( KDDI ) تاريخ الإيداع 18 يونيو 1987، تاريخ المنح 22 ديسمبر 1988 – شويتشي ماتسوموتو، ماساهيرو سايتو – نظام لمنع انتشار الحمل في الترميز الحسابي
براءة اختراع أمريكية رقم 4,933,883 – (شركة آي بي إم) تاريخ الإيداع: 3 مايو 1988، تاريخ المنح: 12 يونيو 1990 – ويليام ب. بينيباكر، جوان ل. ميتشل – تكييف الاحتمالات لمبرمجي العمليات الحسابية
براءة اختراع أمريكية رقم 4,989,000 – (شركة آي بي إم) تم تقديم الطلب في 19 يونيو 1989، وتم منحه في 29 يناير 1991 – دان إس. تشيفيون، إيهود دي. كارنين، يوجينيوس والاش – ضغط سلسلة البيانات باستخدام الترميز الحسابي مع تقدير مبسط لفترة الاحتمالية الفرعية
براءة اختراع أمريكية رقم 5,099,440 – (شركة آي بي إم) تاريخ الإيداع: 5 يناير 1990، تاريخ المنح: 24 مارس 1992 – ويليام ب. بينيباكر، جوان ل. ميتشل – تكييف الاحتمالات لمبرمجي العمليات الحسابية
براءة اختراع أمريكية رقم 5,272,478 – ( ريكو ) تاريخ الإيداع 17 أغسطس 1992، تاريخ المنح 21 ديسمبر 1993 – جيمس د. ألين – طريقة وجهاز لترميز الإنتروبيا

ملاحظة: هذه القائمة غير شاملة. راجع الروابط التالية للاطلاع على قائمة ببراءات اختراع أمريكية أخرى. ^{[ 14 ]} يستخدم برنامج ترميز ديراك الترميز الحسابي وهو ليس قيد انتظار براءة اختراع. ^{[ 15 ]}

قد توجد براءات اختراع خاصة بالترميز الحسابي في ولايات قضائية أخرى؛ انظر براءات اختراع البرمجيات لمناقشة إمكانية الحصول على براءة اختراع للبرمجيات في جميع أنحاء العالم.

المعايير والخصائص التقنية الأخرى

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

ملحوظات

1 2 3 4 5 6 7 8 9 10 11 12 13 ويتن، إيان هـ.؛ نيل، رادفورد م.؛ كليري، جون ج. (يونيو 1987). "الترميز الحسابي لضغط البيانات". اتصالات رابطة آلات الحوسبة . 30 (6): 520-540 . doi : 10.1145/214762.214771 . S2CID 3343393 .
1 2 3 4 شانون، كلود إي. (1948). "نظرية رياضية للاتصالات". مجلة بيل سيستم التقنية . 27 (3): 379-423 . doi : 10.1002/j.1538-7305.1948.tb01338.x .
1 2 3 4 5 6 7 8 كوفير، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات (الطبعة الثانية ). جون وايلي وأولاده. ISBN 978-0-471-24195-9.
↑ ريسانين، جيه جيه؛ لانغدون، جي جي، الابن (مارس 1979). "الترميز الحسابي". مجلة آي بي إم للبحوث والتطوير . 23 (2): 149-162 . doi : 10.1147/rd.232.0149 . S2CID 39909636 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
1 2 3 4 5 6 ريسانين، جورما (مايو 1976). "متباينة كرافت المعممة والترميز الحسابي". مجلة آي بي إم للبحوث والتطوير . 20 (3): 198-203 . doi : 10.1147/rd.203.0198 .
1 2 3 4 5 سيود، خالد (2017). مقدمة في ضغط البيانات (الطبعة الخامسة ). مورغان كوفمان. ISBN 978-0-12-809474-7.
1 2 3 4 5 6 7 هوارد، بول ج.؛ فيتر، جيفري س. (1994)، "الترميز الحسابي لضغط البيانات"، وقائع معهد مهندسي الكهرباء والإلكترونيات ، 82 (6): 857-865 ، doi : 10.1109/5.286189 ، hdl : 1808/7229
↑ هوفمان، ديفيد (1952). "طريقة لإنشاء رموز الحد الأدنى من التكرار". وقائع معهد مهندسي الكهرباء والإلكترونيات (IEEE) . 40 (9). معهد مهندسي الكهرباء والإلكترونيات (IEEE): 1098-1101 . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .
1 2 باسكو، ريتشارد كلارك (مايو 1976). خوارزميات ترميز المصدر لضغط البيانات السريع (أطروحة دكتوراه). جامعة ستانفورد. CiteSeerX 10.1.1.121.3377 .
↑ "ما هو JPEG؟" . ضغط الصور: الأسئلة الشائعة (الجزء 1/3) .
↑ "التوصية T.81 (1992) التصحيح 1 (01/04)" . التوصية T.81 (1992) . الاتحاد الدولي للاتصالات. 9 نوفمبر 2004. تم الاطلاع عليه في 3 فبراير 2011 .
↑ بينيباكر، دبليو بي؛ ميتشل، جيه إل (1992). معيار ضغط بيانات الصور الثابتة JPEG . دار نشر كلوير الأكاديمية. ISBN 0442012721.
↑ "T.81 - الضغط الرقمي وتشفير الصور الثابتة ذات النغمات المتواصلة - المتطلبات والإرشادات" (ملف PDF) . CCITT . سبتمبر 1992. تم الاطلاع عليه بتاريخ 12 يوليو 2019 .
↑ "الأسئلة الشائعة" . comp.compression .
↑ "تم إصدار برنامج ترميز الفيديو Dirac 1.0 [ LWN.net ] " . lwn.net .

مراجع

ماكاي، ديفيد جيه سي (سبتمبر 2003). "الفصل 6: رموز التدفق" . نظرية المعلومات، والاستدلال، وخوارزميات التعلم . مطبعة جامعة كامبريدج . ISBN 0-521-64298-1أُرشف من النسخة الأصلية (PDF/ PostScript / DjVu / LaTeX ) بتاريخ 22 ديسمبر 2007. تم الاطلاع عليه بتاريخ 30 ديسمبر 2007 .
بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "القسم 22.6. الترميز الحسابي" . وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة). نيويورك: مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8أُرشف من المصدر الأصلي بتاريخ 11 أغسطس 2011. تم الاطلاع عليه بتاريخ 18 أغسطس 2011 .
ريسانين، جورما (مايو 1976). "متباينة كرافت المعممة والترميز الحسابي" . مجلة آي بي إم للبحوث والتطوير . 20 (3): 198-203 . doi : 10.1147/rd.203.0198 . تاريخ الاسترجاع: 21 سبتمبر 2007 .
ريسانين، جيه جيه؛ لانغدون، جي جي الابن (مارس 1979). "الترميز الحسابي" (ملف PDF) . مجلة آي بي إم للبحوث والتطوير . 23 (2): 149-162 . doi : 10.1147/rd.232.0149 . S2CID 39909636. مؤرشف من الأصل (ملف PDF) في 28 سبتمبر 2007. تم الاطلاع عليه في 22 سبتمبر 2007 .
ويتن، إيان هـ.؛ نيل، رادفورد م.؛ كليري، جون ج. (يونيو 1987). "الترميز الحسابي لضغط البيانات" ( ملف PDF) . مجلة اتصالات رابطة مكائن الحوسبة . 30 (6): 520-540 . doi : 10.1145/214762.214771 . S2CID 3343393. مؤرشف (ملف PDF) من الأصل في 28 سبتمبر 2007. تم الاطلاع عليه في 21 سبتمبر 2007 .

روديونوف أناتولي، فولكوف سيرجي (2010) "الترميز الحسابي p-adic" الرياضيات المعاصرة، المجلد 508، 2010
روديونوف أناتولي، فولكوف سيرجي (2007) "الترميز الحسابي p-adic"، الترميز الحسابي p-adic
نمذجة اللغة هي ضغط https://arxiv.org/pdf/2309.10668

روابط خارجية

تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "الترميز الحسابي" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .
منشور في مجموعة الأخبار يتضمن مثالاً عملياً قصيراً للترميز الحسابي (الأعداد الصحيحة فقط).
مقال من موقع PlanetMath حول البرمجة الحسابية
تشريح مُشفِّر النطاق: تشرح هذه المقالة كلاً من تشفير النطاق والتشفير الحسابي. كما تتضمن نماذج برمجية لثلاثة أنواع مختلفة من مُشفِّرات التشفير الحسابي، بالإضافة إلى مقارنة الأداء.
مقدمة في الترميز الحسابي، مؤرشفة في 9 نوفمبر 2020 على موقع Wayback Machine . 60 صفحة.
إريك بودن ، ومالتي كلاسن، ويواكيم كنيس: الكشف عن الترميز الحسابي . تقرير فني 2007-5، مجموعة سابل للأبحاث، جامعة ماكجيل.
الترميز الحسابي + النمذجة الإحصائية = ضغط البيانات بقلم مارك نيلسون.
ضغط البيانات باستخدام الترميز الحسابي بقلم مارك نيلسون (2014)
التنفيذ السريع لترميز النطاق و rANS بواسطة جيمس ك. بونفيلد

[Witten1987-1] 1 2 3 4 5 6 7 8 9 10 11 12 13 ويتن، إيان هـ.؛ نيل، رادفورد م.؛ كليري، جون ج. (يونيو 1987). "الترميز الحسابي لضغط البيانات". اتصالات رابطة آلات الحوسبة . 30 (6): 520-540 . doi : 10.1145/214762.214771 . S2CID 3343393 .

[Shannon1948-2] 1 2 3 4 شانون، كلود إي. (1948). "نظرية رياضية للاتصالات". مجلة بيل سيستم التقنية . 27 (3): 379-423 . doi : 10.1002/j.1538-7305.1948.tb01338.x .

[CoverThomas-3] 1 2 3 4 5 6 7 8 كوفير، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات (الطبعة الثانية ). جون وايلي وأولاده. ISBN 978-0-471-24195-9.

[Rissanen1979-4] ريسانين، جيه جيه؛ لانغدون، جي جي، الابن (مارس 1979). "الترميز الحسابي". مجلة آي بي إم للبحوث والتطوير . 23 (2): 149-162 . doi : 10.1147/rd.232.0149 . S2CID 39909636 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[Rissanen1976-5] 1 2 3 4 5 6 ريسانين، جورما (مايو 1976). "متباينة كرافت المعممة والترميز الحسابي". مجلة آي بي إم للبحوث والتطوير . 20 (3): 198-203 . doi : 10.1147/rd.203.0198 .

[Sayood2017-6] 1 2 3 4 5 سيود، خالد (2017). مقدمة في ضغط البيانات (الطبعة الخامسة ). مورغان كوفمان. ISBN 978-0-12-809474-7.

[Howard1994-7] 1 2 3 4 5 6 7 هوارد، بول ج.؛ فيتر، جيفري س. (1994)، "الترميز الحسابي لضغط البيانات"، وقائع معهد مهندسي الكهرباء والإلكترونيات ، 82 (6): 857-865 ، doi : 10.1109/5.286189 ، hdl : 1808/7229

[Huffman1952-8] هوفمان، ديفيد (1952). "طريقة لإنشاء رموز الحد الأدنى من التكرار". وقائع معهد مهندسي الكهرباء والإلكترونيات (IEEE) . 40 (9). معهد مهندسي الكهرباء والإلكترونيات (IEEE): 1098-1101 . doi : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .

[Pasco1976-9] 1 2 باسكو، ريتشارد كلارك (مايو 1976). خوارزميات ترميز المصدر لضغط البيانات السريع (أطروحة دكتوراه). جامعة ستانفورد. CiteSeerX 10.1.1.121.3377 .

[10] "ما هو JPEG؟" . ضغط الصور: الأسئلة الشائعة (الجزء 1/3) .

[11] "التوصية T.81 (1992) التصحيح 1 (01/04)" . التوصية T.81 (1992) . الاتحاد الدولي للاتصالات. 9 نوفمبر 2004. تم الاطلاع عليه في 3 فبراير 2011 .

[12] بينيباكر، دبليو بي؛ ميتشل، جيه إل (1992). معيار ضغط بيانات الصور الثابتة JPEG . دار نشر كلوير الأكاديمية. ISBN 0442012721.

[t81-13] "T.81 - الضغط الرقمي وتشفير الصور الثابتة ذات النغمات المتواصلة - المتطلبات والإرشادات" (ملف PDF) . CCITT . سبتمبر 1992. تم الاطلاع عليه بتاريخ 12 يوليو 2019 .

[14] "الأسئلة الشائعة" . comp.compression .

[15] "تم إصدار برنامج ترميز الفيديو Dirac 1.0 [ LWN.net ] " . lwn.net .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]،

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗

1.	تم تحديد ترددات الأحرف.
2.	يتم تقسيم الفترة [0، 1) بنسبة الترددات.
3-5.	يتم تقسيم الفاصل الزمني المقابل بشكل متكرر لكل حرف في الرسالة.
6.	يتم اختيار أي قيمة في الفترة النهائية لتمثيل الرسالة.
2–6.	التقسيم والقيمة إذا كانت الرسالة "كيوي" بدلاً من ذلك.