الحد الأدنى لمتوسط ​​طول كلمة المرور. الترميز. وحدات المعلومات

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

مؤشر الاقتصاد أو كفاءة الشفرة غير المتساوية ليس طول كلمات الكود الفردية ، ولكن "متوسط" طولها ، الذي تحدده المساواة:

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

الأكثر اقتصادا هو الكود مع أصغر متوسط ​​طول. دعنا نقارن بالأمثلة فعالية تكلفة الطرق المختلفة لتشفير نفس المصدر.

دع المصدر يحتوي على 4 رسائل مع الاحتمالات. يمكن تشفير هذه الرسائل بكلمات تشفير ذات طول ثابت ، وتتكون من حرفين ، في الأبجدية وفقًا لجدول الكود.

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

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

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

عند استخدام الرموز غير الموحدة ، تظهر مشكلة ، سنشرحها باستخدام مثال جدول الكود الأخير. دع هذا الجدول يشفر سلسلة من الرسائل ، ونتيجة لذلك يتم تحويله إلى النص الثنائي التالي: 010110. تم فك تشفير الحرف الأول من الرسالة الأصلية بشكل لا لبس فيه - وهذا هو. ومع ذلك ، يبدأ المزيد من عدم اليقين: إما . هذه ليست سوى بعض الخيارات الممكنة لفك تشفير تسلسل الأحرف الأصلي.

وتجدر الإشارة إلى أن الغموض في فك تشفير الكلمات ظهر على الرغم من حقيقة أن شرط فك تشفير الأحرف الفريد (حقن تعيين الشفرة) قد تم الوفاء به.

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

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

ضع في اعتبارك الكود (مخطط الترميز الأبجدي) ، من خلال جدول الكود

والعديد من الكلمات المكونة من رموز أولية.

تعريف. يسمى الكود بشكل فريد إذا كان

أي أن أي كلمة تتكون من رموز أولية تتحلل بشكل فريد إلى أكواد أولية.

إذا كان جدول الكود يحتوي على نفس كلمات الكود ، فهذا يعني ، إذا

إذن فالشفرة ليست قابلة للفك بشكل فريد (الدائرة غير قابلة للفصل). لم تتم مناقشة هذه الرموز بشكل أكبر.

رموز البادئة

إن أبسط الأكواد وأكثرها استخدامًا بدون فاصل كلمات مشفرة خاصة هي ما يسمى برموز البادئة.

تعريف . يُطلق على الكود الذي يحتوي على خاصية أنه لا توجد كلمة رمزية هي بداية (بادئة) كلمة رمز أخرى البادئة.

نظرية 1.رمز البادئة قابل للفك بشكل فريد.

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

معلومة - هذه مجموعة من المعلومات يتم تخزينها ونقلها ومعالجتها واستخدامها في الأنشطة البشرية.

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

يميز نوعان من الإشارات (وبالتالي نوعان من الرسائل ): مستمر ومنفصل.

لضمان بساطة وموثوقية التعرف على إشارات من نوع منفصل ( علامات ) ، يجب تقليل عددهم إلى الحد الأدنى. كقاعدة عامة ، يلجأون إلى عملية تمثيل الأحرف الأصلية بأبجدية مختلفة بعدد أقل من الأحرف ، تسمى حرف او رمز . عند تعيين هذه العملية ، يتم استخدام المصطلح نفسه - " الترميز ».

المعلومات الخاصة

مقدار المعلومات التي تحملها الرسالة x أناالأبجدية ، دعنا ندعو المعلومات الخاصة الواردة في x أناوالدلالة
.

.

صيغة شانون

نحن نصنف معلوماتنا الخاصة ، أي احسب متوسط ​​كمية المعلومات التي يحملها حرف واحد من الأبجدية
:
.

متوسط ​​كمية المعلوماتالمتعلقة بحرف واحد، يسمى إنتروبيا الأبجدية (أو المصدر)والمشار إليها ح:

- صيغة شانون .

من الواضح أن معدل 1 كمية المعلومات في طول الرسالة ن محسوبة بالصيغة:

.

تعليق.يُنسب مقدار المعلومات إلى الرسالة نفسها.

تعليق. الانتروبيا هي خاصية مميزة لمصدر الرسالة (الأبجدية).

صيغة هارتلي

في قابلية التجهيزالحروف الأبجدية
من صيغة شانون نحصل عليها:.

- صيغة هارتلي .

وحدات المعلومات

يتم استدعاء وحدة مقدار المعلومات لكل عنصر رسالة (وحدة إنتروبيا) قليل .

ضع في اعتبارك أبجدية من الرموز القابلة للتجهيز التي تساوي إنتروبيا 1:
. لأنه يتبع من هنا
، من الواضح أن 1 بت هو مقدار المعلومات الموجودة في رسالة ثنائية (الأبجدية (0،1)) بطول 1.

فيما يلي ، في التعابير الخاصة بـ I و H ، سنستخدم دائمًا اللوغاريتمات ذات الأساس 2.

خصائص الانتروبيا

1. الانتروبيا ح- ضخامة

- غير سلبي(ح  0) ,

- محدود, تنبع هذه الخصائص من حقيقة أن جميع شروطها لها نفس الخصائص.
.

2. إنتروبيا تساوي صفرًا إذا كان احتمال أحد الرموز يساوي 1. في هذه الحالة ، يتحدث المرء عن مصدر حتمي تمامًا وغياب عدم اليقين فيه ، حيث يعرف الراصد عن رسالة المصدر حتى لحظة ملاحظته.

3. ويمكن أيضا أن تظهر أن الانتروبيا الحد الأقصى إذا كانت جميع أحرف الأبجدية متساوية في الاحتمال، بمعنى آخر. حماكس = سجل م. وبالتالي ، للعثور على أقصى قيمة ممكنة للإنتروبيا (لعدد ثابت من الأحرف) ، يتم استخدام صيغة هارتلي.

4. ذات أهمية خاصة الرسائل الثنائيةاستخدام ثنائي الأبجدية(0.1). منذ في م= 2 احتمالية الأحرف الأبجدية ص 1  1 و ص 2  1 ، ثم يمكننا وضعها ص 1 = صو ص 2 = 1-ص. ثم يتم تحديد الانتروبيا من خلال العلاقة

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

لتنزيل أرشيف بمستند ، أدخل رقمًا مكونًا من خمسة أرقام في الحقل أدناه وانقر على الزر "تنزيل الأرشيف"

وثائق مماثلة

العدد الإجمالي للرسائل غير المكررة. حساب معدل نقل المعلومات وعرض النطاق الترددي لقنوات الاتصال. تعريف تكرار الرسائل والترميز الأمثل. الإجراء الخاص بإنشاء الكود الأمثل وفقًا لطريقة Shannon-Fano.

ورقة مصطلح ، تمت الإضافة بتاريخ 04/17/2009


وصف وميزات بعض خوارزميات الأرشفة. بناء كود هوفمان. خوارزمية ديناميكية لبناء كود هوفمان. استعادة النص العكسي. طرق ترميز المعلومات على مرحلتين. التنفيذ العملي لخوارزمية LZ77.

ورقة مصطلح ، تمت الإضافة 12/24/2012


تقدير التعقيد الحسابي للبرنامج. تنفيذ خوارزمية Huffman Information Coding. ترميز الاختبار في كود ثنائي وفي شجرة هوفمان. رمز الأحرف الثنائية. الرمز وتكرار حدوثه في النص. حساب مدى تعقيد الخوارزمية.

التحكم في العمل ، تمت إضافة 12/16/2012


تحديد متوسط ​​كمية المعلومات. الاعتماد بين رموز مصفوفة الاحتمالات الشرطية. الترميز بطريقة شانون فانو. معدل نقل قناة الاتصال. كفاءة تشفير الرسائل بطريقة د. هوفمان ، خصائص الكود.

الاختبار ، تمت إضافة 05/04/2015


التعريف بمفاهيم الكود والترميز وفك التشفير وأنواعه وقواعده ومهامه. تطبيق نظريات شانون في نظرية الاتصال. التصنيف والمعلمات وبناء أكواد تصحيح الأخطاء. طرق نقل الرموز. مثال على بناء كود شانون.

ورقة مصطلح ، تمت الإضافة في 02/25/2009


تحليل فعالية طرق الترميز. متوسط ​​حجم بت واحد ومتوسط ​​طول كلمة الشفرة. ترميز هوفمان. ترميز المعلومات حسب طريقة Shanon-Fano. بناء شجرة كود لمختلف طرق التشفير.

التحكم في العمل ، تمت إضافة 10/15/2013


التشفير وفك التشفير ، وتحويل رسالة منفصلة إلى إشارة منفصلة. بناء نموذج رياضي للكود التصحيحي. إنشاء مصفوفة كود المعلومات. الهيكل المعياري للبرنامج. مواصفات وحدات البرنامج.

ورقة مصطلح ، تمت إضافة 11/28/2014

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

مؤشر الاقتصاد أو كفاءة الشفرة غير المتساوية ليس طول كلمات الكود الفردية ، ولكن "متوسط" طولها ، الذي تحدده المساواة:

أين هي كلمة الشفرة التي قامت بتشفير الرسالة ، وطولها ، هو احتمال الرسالة ، هو العدد الإجمالي لرسائل المصدر. من أجل الإيجاز في كتابة الصيغ ، يمكن استخدام الترميز التالي و . لاحظ أن تعيين متوسط ​​طول التشفير على أنه يؤكد حقيقة أن هذه القيمة تعتمد على كل من مصدر الرسالة وطريقة التشفير.

الأكثر اقتصادا هو الكود مع أصغر متوسط ​​طول. دعنا نقارن بالأمثلة فعالية تكلفة الطرق المختلفة لتشفير نفس المصدر.

دع المصدر يحتوي على 4 رسائل مع الاحتمالات. يمكن تشفير هذه الرسائل بكلمات تشفير ذات طول ثابت ، وتتكون من حرفين ، في الأبجدية وفقًا لجدول الكود.

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

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

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

عند استخدام الرموز غير الموحدة ، تظهر مشكلة ، سنشرحها باستخدام مثال جدول الكود الأخير. دع هذا الجدول يشفر سلسلة من الرسائل ، ونتيجة لذلك يتم تحويله إلى النص الثنائي التالي: 010110. يتم فك الرمز الأول من الرسالة الأصلية بشكل لا لبس فيه - هذا. ومع ذلك ، يبدأ المزيد من عدم اليقين: أو . هذه ليست سوى بعض الخيارات الممكنة لفك تشفير تسلسل الأحرف الأصلي.

وتجدر الإشارة إلى أن الغموض في فك تشفير الكلمات ظهر على الرغم من حقيقة أن شرط فك تشفير الأحرف الفريد (حقن تعيين الشفرة) قد تم الوفاء به.

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

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

ضع في اعتبارك الكود (مخطط الترميز الأبجدي) ، من خلال جدول الكود

والعديد من الكلمات المكونة من رموز أولية.

تعريف. يسمى الكود بشكل فريد إذا كان

أي أن أي كلمة تتكون من رموز أولية تتحلل بشكل فريد إلى أكواد أولية.

إذا كان جدول الكود يحتوي على نفس كلمات الكود ، فهذا يعني ، إذا

إذن فالشفرة ليست قابلة للفك بشكل فريد (الدائرة غير قابلة للفصل). لم تتم مناقشة هذه الرموز بشكل أكبر.

تتم كتابة رسائل الأبجدية المصدر بترتيب تنازلي لاحتمالات حدوثها. ثم يتم تقسيمها إلى جزأين بحيث تكون الاحتمالات الإجمالية للرسائل في كل جزء من هذه الأجزاء ، إن أمكن ، متماثلة تقريبًا. يتم تعيين رسائل الجزء الأول 0 كحرف أول ، ويتم تعيين رسائل الجزء الثاني 1 (والعكس صحيح). ثم يتم تقسيم كل جزء من هذه الأجزاء (إذا كان يحتوي على أكثر من رسالة واحدة) إلى جزأين متساويين في الاحتمال ، ويتم أخذ 0 كرمز ثانٍ للجزء الأول ، و 1 للجزء الثاني. وتتكرر هذه العملية حتى كل جزء من الأجزاء المستلمة لا تحتوي على رسالة واحدة في كل مرة. للمثال الوارد في الجدول. 1 في المرحلة الأولى من تقسيم الجزء الأول سيكون هناك رسالة واحدة أ 1 مع الاحتمال ص(أ 1) = 0.4 ، في الجزء الثاني - الرسائل المتبقية باحتمالية إجمالية ص Σ ( أ 2 -أ 6) = 0.6. دعونا ننسب الرسالة أحرف واحد 0 ، وبقية الرسائل كالحرف الأول - 1.

الجدول 1. ترميز الرسائل التعسفية

في المرحلة الثانية نقوم بفصل الرسائل ( أ 2 ,أ 3 ,أ 4 ,أ 5 ,أ 6) إلى جزأين متساويين في الاحتمال ، بما في ذلك الجزء الأول من الرسالة أ 2 ، وفي الجزء الثاني - الرسائل ( أ 3 ,أ 4 ,أ 5 ,أ 6). دعونا ننسب الرسالة أ 2 كالحرف الثاني 0 ، وبقية الرسائل - 1 ، وهكذا. نتيجة لذلك ، وصلنا إلى الكود إلى 2 ، الواردة في الجدول. 2.

الجدول 2. ترميز شانون فانو للرسائل

الكود ببنائه يتوافق مع خاصية البادئة. لذلك ، فإن التسلسل أعلاه للأحرف الثنائية " إل "بشكل لا لبس فيه: ( أ 1 ,أ 1 ,أ 4 ,أ 1 ,أ 1 ,أ 1 ,أ 6 ,أواحد). متوسط ​​عدد الأحرف لكل رسالة ، مع مراعاة احتمالاتها \ u003d 0.4 * 1 + 0.3 * 2 + 0.3 * 4 \ u003d 2.2 ، أي يتجاوز قليلاً إنتروبيا مصدر الرسالة.

2.4 متوسط ​​طول كلمة السر

لا يقلل إجراء شانون فانو بالضرورة ، نظرًا لأن تحقيق قيمة كبيرة لمتوسط ​​المعلومات الخاصة على حرف رمز واحد يمكن أن يؤدي إلى استنفاد الاختيار لأحرف الكود اللاحقة. إذا كان من الممكن حساب هذا القسم بحيث تكون المجموعات قابلة للتجهيز تمامًا في كل مرحلة من مراحل القسم ، فإن احتمالات الأحرف المصدر وأطوال الكلمات المشفرة مرتبطة بـ

(2)

القيود المفروضة على أطوال كلمات التشفير لرمز البادئة مقدمة من عدم المساواة في Kraft ونظرية التشفير للمصدر.

نظرية 1.(عدم المساواة في كرافت). إذا كانت الأعداد الصحيحة (
) تفي بعدم المساواة

(3)

ثم يوجد رمز له خاصية البادئة بأحرف أبجدية بالحجم D ، أطوال الكلمات المشفرة التي تساوي هذه الأرقام. على العكس من ذلك ، فإن أطوال الكلمات المشفرة لأي كود يفرض خاصية البادئة تفي بعدم المساواة (3). لا تنص النظرية على أن أي كود بأطوال كلمة مشفرة مرضية (3) هو بادئة. لذلك ، على سبيل المثال ، مجموعة كلمات الشفرة الثنائية (0 ؛ 00 ؛ 11) ترضي (3) ، لكن ليس لها خاصية البادئة. تنص النظرية على وجود بعض كود البادئة بمثل هذه الأطوال ، مثل الكود (0 ؛ 10 ؛ 11). ليس أي كود فك تشفير لا لبس فيه له خاصية البادئة ، على سبيل المثال ، كود K3 للجدول. 3. في ذلك ، كل كلمة رمزية هي بادئة لكل كلمة رمزية أطول. في الوقت نفسه ، يعد تفرد فك التشفير أمرًا تافهًا ، نظرًا لأن الرمز 0 يحدد دائمًا بداية كلمة رمز جديدة. تختلف الرموز التي تحتوي على خاصية البادئة ، مع ذلك ، عن الرموز الأخرى القابلة للفك بشكل فريد من حيث أنه يمكن دائمًا التعرف على نهاية كلمة التشفير ، بحيث يمكن إجراء فك التشفير دون تأخير التسلسل الملحوظ لكلمات التشفير (الكود K4 في الجدول 3). لهذا السبب ، تسمى رموز البادئة أحيانًا الرموز الفورية.

الجدول 3. الرموز الفريدة لفك التشفير

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