يجب أن تتوافق الشفرة مع خاصية فك التشفير بشكل لا لبس فيه. EGE في المعلوماتية ، مهمة A9 ، Polyakov K

موضوع: ترميز وفك شفرة المعلومات

تحقق من العناصر : القدرة على ترميز و دي ترميز المعلومات

المادة النظرية :

الترميز - هي ترجمة المعلومات من لغة إلى أخرى (الكتابة في نظام آخر من الرموز ، بأحرف أبجدية أخرى).

يمكن فك ترميز الرسالة المشفرة بشكل فريد من البداية إذا كان حالة فانو: لا يوجد كلمة مشفرة هي بداية كلمة شيف أخرى.

يمكن فك ترميز الرسالة المشفرة بشكل فريد من النهاية إذا كان حالة عكس انو: لا يوجد codeword هو نهاية كلمة أخرى.

تعد حالة Fano شرطًا كافيًا ولكن ليس ضروريًا لفك تشفير لا لبس فيه.

مثال المهمة:

لترميز تسلسل يتكون من الأحرف A و B و C و D و D ، قررنا استخدام شفرة ثنائية غير متساوية تسمح لنا بفك تشفير التسلسل الثنائي الذي يظهر على جانب استقبال قناة الاتصال بشكل فريد. الرمز المستخدم هو A - 1، B - 000، B - 001، D - 011. حدد الكلمة البرمجية للحرف D.

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

النهج العام:

استخدام حالة Fano أو التفكير المنطقي للعثور على الإجابة.

الحل:

1) 00 - ينتهك حالة Fano ، بما أن تتطابق سلسلة التعليمات البرمجية مع بداية B = 000 و B = 001. من المستحيل فك تشفير السلسلة 000000 بشكل لا لبس فيه: يمكن أن يكون DDD أو BB ، بحيث لا يتناسب الخيار الأول

2) 01 - ينتهك حالة Fano ، منذ ذلك الحين تتطابق سلسلة التعليمات البرمجية مع بداية T = 011. H من المستحيل فك تشفير السلسلة 011 بشكل لا لبس فيه: يمكن أن يكون YES أو T ، لذا فإن الخيار الثاني غير مناسب أيضًا

3) 11 - ينتهك حالة Fano ، منذ ذلك الحين تتطابق سلسلة التعليمات البرمجية مع بداية A = 1. Nمن المستحيل فك تشفير السلسلة 111 بشكل لا لبس فيه: هذا يمكن أن يكون YES أو AAA ؛ الخيار الثالث لا يصلح

4) 010 - لم يتم انتهاك حالة فانو.

الجواب: 4) 010

مهام للتدريب:

1) لنقل عبر قناة اتصال لرسالة تتكون فقط من الأحرف A ، B ، C ، D ، قرروا استخدام رمز غير متساوٍ في الطول: A = 00 ، B = 11 ، C = 100. كيف ينبغي تشفير الحرف G بحيث يكون طول الشفرة ضئيلاً ويُسمح بتجزئة الرسائل المشفرة؟

2) للإرسال عبر قناة اتصال لرسالة تتكون فقط من الأحرف A ، B ، C ، D ، قرروا استخدام رمز غير متساوٍ في الطول: A = 1 ، B = 000 ، C = 001. كيف ينبغي تشفير الحرف G بحيث يكون طول الشفرة ضئيلاً ويُسمح بتجزئة الرسائل المشفرة؟

3) لترميز تسلسل يتكون من الأحرف A و B و C و D و D ، يتم استخدام رمز ثنائي غير متساوٍ ، مما يسمح لك بفك تشفير التسلسل الثنائي الناتج بشكل فريد. إليك هذا الكود: A - 10، B - 11، B - 000، D - 001، D - 011. هل من الممكن اختصار طول كلمة الرمز لأحد الأحرف بحيث يمكن فك الشفرة بشكل لا لبس فيه؟ لا ينبغي تغيير رموز الأحرف المتبقية. اختر الإجابة الصحيحة.

1) إنه مستحيل

2) للحرف B - 1

3) للحرف B - 00

4) للحرف د - 01

4) لترميز تسلسل معين يتكون من الأحرف A و B و C و D و D ، يتم استخدام شفرة ثنائية غير متساوية ، مما يسمح بفك ترميز التسلسل الثنائي الناتج بشكل لا لبس فيه. إليك هذا الكود: A - 11، B - 10، B - 011، D - 000، D - 001. هل من الممكن اختصار طول كلمة الرمز لأحد الأحرف بحيث يمكن فك الشفرة بشكل لا لبس فيه؟ لا ينبغي تغيير رموز الأحرف المتبقية. اختر الإجابة الصحيحة.

1) للحرف G-00

2) إنه مستحيل

3) للحرف B - 01

4) للحرف B - 1

5) لترميز تسلسل يتكون من الأحرف A و B و C و D و D ، يتم استخدام رمز ثنائي غير متساوٍ ، مما يسمح لك بفك تشفير التسلسل الثنائي الناتج بشكل فريد. إليك هذا الكود: A - 10، B - 001، B - 0001، D - 110، D - 111. هل من الممكن اختصار طول كلمة الرمز لأحد الأحرف بحيث يمكن فك الشفرة بشكل لا لبس فيه؟ لا ينبغي تغيير رموز الأحرف المتبقية. اختر الإجابة الصحيحة.

1) للحرف G - 11

2) إنه مستحيل

3) للحرف B - 000

لترميز تسلسل معين يتكون من الأحرف A و B و C و D و D و E ، قررنا استخدام شفرة ثنائية غير متساوية تفي بشرط Fano. بالنسبة للحرف A ، تم استخدام الكلمة code 0 ؛ للحرف B ، الكلمة البرمجية 10. ما هو أصغر مجموع ممكن أطوال كل كلمات الأكواد الستة؟
ملاحظة. تعني حالة Fano أنه لا يوجد codeword هو بداية كلمة codeword أخرى. هذا يسمح بفك تشفير الرسائل المشفرة.

الخيار مظاهرة EGE 2017 - مهمة رقم 5

الحل:

للعثور على الكلمات البرمجية سنستخدم هذا الجدول.

إذا كانت رموز الأحرف المتبقية تبدأ عند 0 ، فستكون شفرة الحرف A = 0 هي بداية رموزها ، لذا فإن هذا الخيار غير مناسب. إذا كان الرمز B = 10 ، تبدأ رموز الأحرف C و D و D و E في 11. للحصول على 4 رموز مختلفة ، تحتاج إلى استخدام الأكواد المكونة من 4 أحرف (1111 ، 1110 ، 1101 ، 1100).

0	1
	1
	1		0
	1	0	1	0

A - 0 (حرف واحد)
ب - 10 (حرفان)
ب - 1100 (4 أحرف)
G - 1101 (4 أحرف)
D - 1110 (4 أحرف)
E - 1111 (4 أحرف)

1+2+4+4+4+4 = 19

الجواب: 19

الخيار مظاهرة EGE 2016 - مهمة رقم 5

تنقل قناة الاتصالات رسائل تحتوي على أربعة أحرف فقط: P ، O ، C ، T ؛ بالنسبة إلى الإرسال ، يتم استخدام رمز ثنائي يسمح بفك الشفرة بشكل لا لبس فيه. بالنسبة للحروف T ، O ، P ، يتم استخدام كلمات الأكواد التالية: T: 111 ، O: 0 ، P: 100.

حدد أقصر كلمة شفرة للحرف C ، حيث تسمح الشفرة بفك ترميز لا لبس فيه. إذا كان هناك العديد من هذه الأكواد ، حدد الكود ذو القيمة العددية الأدنى.

الحل:

للعثور على الكلمات البرمجية سنستخدم هذا النظام.

إذا بدأت رموز الأحرف المتبقية 0 رمز الرسالة يا=0 ستكون بداية رموزهم ، لذلك هذا الخيار غير مناسب. منذ رمز الرسالة P=100 ورمز الحرف تي =111 ثم الرسالة C لا يمكن أن تبدأ وتنتهي بهذه الأرقام.

الجواب: 101

لترميز رسالة تتكون فقط من الأحرف A و B و C و D ، فإن الشفرة الثنائية غير متساوية الطول:

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

1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16

الحل:

GAVBGV = 0110001011011010

0110	0010	1101	1010
6	2	D	A

الجواب: 4

يتم تشفير الصورة النقطية بالأبيض والأسود سطرًا سطراً ، بدءً من الزاوية العلوية اليمنى وتنتهي في الزاوية اليمنى السفلى. عند الترميز ، 1 يشير إلى أسود و 0 يشير إلى الأبيض.

لالاكتمال ، تم تسجيل النتيجة في الترميز الثماني. اختر إدخال الرمز الصحيح.

1) 57414 2) 53414 3) 53412 4) 53012

الحل:

1	0	1	0	1
1	1	0	0	0
0	1	0	1	0

101	011	100	001	010
5	3	4	1	2

الجواب: 3

لإرسال الأرقام عبر قناة صاخبة ، يتم استخدام رمز التحقق من التماثل. تتم كتابة كل من أرقامه في التمثيل الثنائي ، مع الأصفار الرائدة حتى طول 4 ، ويضاف مجموع عناصره modulo 2 إلى التسلسل الناتج (على سبيل المثال ، إذا تمررنا 23 ، فإننا نحصل على التسلسل 0010100110). تحديد ما هو الرقم الذي تم نقله من خلال القناة في النموذج 01100010100100100110؟

1) 6543 2) 62926 3) 62612 4) 3456

الحل:

01100010100100100110

01100	01010	01001	00110
6	5	4	3

الجواب: 1

لترميز الحروف O ، L ، A ، G ، K ، يتم استخدام الرموز الثنائية للأرقام 0 ، 1 ، 2 ، 3 و 4 ، على التوالي ، (مع صفر واحد غير مهم في حالة تمثيل بت واحد). إذا كانت هذه الطريقة لتشفير تسلسل من الأحرف VOKOLKA وكتابة النتيجة بالرمز السداسي العشري ، تحصل على:

1) 4531253 2) 9876 3) E832 4) 238E

الحل:

يا	L	A	W	K
0=00	1=01	2=10	3=11	4=100

COUNT = 1110100000110010

1110	1000	0011	0010
E	8	3	2

الجواب: 3

لنقل الإرسال عبر قناة اتصال لرسالة تتكون فقط من الأحرف A ، B ، C ، D ، قرروا استخدام رمز غير متساوٍ في الطول: A = 00 ، B = 11 ، C = 100. كيف ينبغي تشفير الحرف G بحيث يكون طول الشفرة ضئيلاً ويُسمح بتجزئة الرسائل المشفرة؟

1) 010 2) 0 3) 01 4) 011

الحل:

A = 00، B = 11، C = 100، D =؟

الجواب: 3

لترميز تسلسل يتكون من الأحرف A و B و C و D و D ، قررنا استخدام شفرة ثنائية غير متساوية تسمح لنا بفك تشفير التسلسل الثنائي الذي يظهر على جانب استقبال قناة الاتصال بشكل فريد. للحروف A و B و C و D استخدمت كلمات الرموز التالية: A - 111، B - 110، C - 101، D - 100.

حدد الكلمة البرمجية من القائمة أدناه لترميز الحرف D.

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

1) 1 2) 0 3) 01 4) 10

الحل:

A - 111، B - 110، B - 101، D - 100، D -؟

الجواب: 2

تنقل قناة الاتصال الرسائل التي تحتوي على 4 أحرف فقط: تستخدم كلمات A ، B ، C ، G. 5 بت لترميز الحروف A ، B ، C: A - 10110 ، B - 11000 ، C - 00101. لهذه المجموعة من الكلمات الرمزية تم تحقيق الخاصية التالية: تختلف كلمتين من المجموعة في ثلاثة مواضع على الأقل. هذه الخاصية مهمة لفك تشفير الرسائل في وجود تداخل. أي من كلمات الشفرة التالية يمكن استخدامها للحرف G ، بحيث يحتفظ الموقع المحدد بكلمات الأكواد الأربعة؟

1) 01110 2) 01011 3) 10001 4) لا تنطبق أي كلمة من الكلمات الواردة أعلاه

الحل:

1) 01 110: A - 10 110 - لا تختلف في ثلاثة مواقع على الأقل

2) 01011: A - 101 10، B - 1 1000، B - 0010 1 - تختلف في ثلاثة مواضع على الأقل

الجواب: 2

بالنسبة لنقل البيانات عبر قناة اتصال ، يتم استخدام رمز 5 بت. تحتوي الرسالة على الأحرف A و B و C فقط ، والتي تم ترميزها بواسطة كلمات التعليمات البرمجية التالية:

A - 10001، B - 01101، B - 10110.

انتقال قد يسبب تداخل. ومع ذلك ، يمكن أن تحاول بعض الأخطاء إصلاحها. أي اثنين من هذه الكلمات رمز الثلاثة تختلف عن بعضها البعض في ما لا يقل عن ثلاث وظائف. لذلك ، إذا حدث خطأ في نقل كلمة ما في ما لا يزيد عن موضع واحد ، فمن الممكن عمل افتراض معقول حول الرسالة التي تم نقلها. (يقال إن "الرمز يصحح خطأً واحداً.") على سبيل المثال ، إذا تم تلقي كلمة السر 01111 ، فيعتبر أن الحرف B قد تم إرساله. (الفرق بين كلمة الشفرة لـ B هو في موضع واحد فقط ، وبالنسبة إلى كلمات الشفرة الأخرى ، هناك اختلافات أكثر). ونظرًا لأن الكلمة تختلف عن كلمات الشفرة للحروف A و B و C في أكثر من موضع ، فمن المعتبر أن يحدث خطأ (يشار إليه بـ "x").

تم استلام الرسالة 00110 11101 11000 11001. قم بفك شفرة هذه الرسالة - حدد الخيار الصحيح.

1) VBHH 2) ABBVA 3) xxxx 4) VBHA

الحل:

00110	11101	11000	11001
ب = 1،0110	B = 0 1101	س	أ = 10 001

الجواب: 4

لترميز تسلسل معين يتكون من الأحرف A و B و C و D و D ، يتم استخدام رمز ثنائي غير متساوي ، مما يسمح بفك ترميز التسلسل الثنائي الناتج بشكل فريد. هذا هو الرمز: A - 1؛ ب - 0100 ب - 000 ز - 011 ؛ D - 0101. يجب تقصير طول كلمة الرمز لأحد الأحرف بحيث يمكن فك الشفرة بشكل فريد. لا ينبغي تغيير رموز الأحرف المتبقية. أي من الطرق التالية يمكن القيام بها؟

A-1، B-011، B-00، G-010

الجواب: 9

تنقل قناة الاتصال الرسائل ، وتحتوي كل منها على 15 حرفًا A و 10 أحرف B و 6 أحرف C و 4 أحرف D (لا توجد رسائل أخرى في الرسائل). يتم ترميز كل حرف في تسلسل ثنائي. عند اختيار رمز ، تم أخذ اثنين من المتطلبات في الاعتبار:

أ) لا توجد كلمة شفرة هي بداية أخرى (من الضروري أن تسمح الشفرة بفك تشفير لا لبس فيه) ؛

ب) يجب أن يكون الطول الإجمالي للرسالة المشفرة أقصر ما يمكن.

ما هو الرمز التالي الذي ينبغي اختياره لترميز الأحرف A و B و C و D؟

1) A: 1، B: 01، B: 001، D: 111

2) A: 1، B: 01، C: 10، D: 111

3) A: 00 ، B: 01 ، C: 10 ، D: 11

4) A: 100 ، B: 101 ، C: 11 ، D: 0

الحل:

لا يوجد كلمة مشفرة هي بداية أخرى: A هي البداية D في الإصدارين الأول والثاني.

يجب أن يكون الطول الإجمالي للرسالة المشفرة قصيرًا قدر الإمكان.

3) A: 00 (15)، B: 01 (10)، B: 10 (6)، D: 11 (4)

2.15+2.10+2.6+2.4 = 70

4) A: 100 (15) و B: 101 (10) و B: 11 (6) و D: 0 (4)

3.15+3.10+2.6_1.4 = 61

الجواب: 3

تستخدم قناة الاتصال رمزًا ثنائيًا موحدًا لإرسال رسائل تحتوي على 4 أحرف فقط P ، P ، C ، T. تتطابق كل حرف مع كلمة التعليمات البرمجية الخاصة بها ، ويتم استيفاء الخاصية التالية لمجموعة من كلمات الرموز: تختلف كلمتين من المجموعة على الأقل ثلاث وظائف. هذه الخاصية مهمة لفك تشفير الرسائل في وجود تداخل. لترميز الحروف P ، P ، C ، يتم استخدام كلمات الرموز 5 بت: P: 01111 ، P: 00001 ، C: 11000. يبدأ رمز 5 بت للحرف T في 1 وينتهي في 0. تحديد كلمة الرمز للحرف T.

الحل:

ج: 1 1000

تي: 0101 0 (يبدأ T في 1 وينتهي في 0)

C و T: حرفان متشابهان ، وهذا يعني أن الأحرف الثلاثة الأخرى يجب أن تكون مختلفة.

الإجابة: 1 0110

امتحان موحد للدولة في علوم الكمبيوتر ، مهمة A9 ، Polyakov K.

لترميز تسلسل معين يتكون من الأحرف A و B و C و D و D ، يتم استخدام رمز ثنائي غير متساوي ، مما يسمح بفك ترميز التسلسل الثنائي الناتج بشكل فريد. إليك هذا الكود: A - 00، B - 010، B - 011، D - 101، D - 111. هل من الممكن اختصار طول كلمة الرمز لأحد الأحرف بحيث يمكن فك الشفرة بشكل لا لبس فيه؟ لا ينبغي تغيير رموز الأحرف المتبقية. اختر الإجابة الصحيحة.

أمثلة على ذلك.
1. لترميز تسلسل يتكون من الأحرف A و B و C و D و D ، قررنا استخدام شفرة ثنائية غير متساوية تسمح لنا بفك تشفير التسلسل الثنائي الذي يظهر على جانب استقبال قناة الاتصال بشكل فريد. الكود المستخدم:
A - 1، B - 000، B - 001، D - 011. حدد الكلمة البرمجية للحرف D. يجب أن يكون طول كلمة الشفرة هذه هو أصغر حجم ممكن. يجب أن تتوافق الشفرة مع خاصية فك التشفير بشكل لا لبس فيه.
1) 00 2) 01 3)11 4) 010
الحل:
8) لاحظ أنه بالنسبة لجزء معروف من الشفرة ، تتحقق حالة Fano - لا توجد كلمة code هي بداية كلمة شفرة أخرى
9) إذا كانت D = 00 ، تتطابق سلسلة الشفرة هذه مع بداية B = 000 و B = 001 ، فمن المستحيل فك تشفير السلسلة 000000 بشكل لا لبس فيه: يمكن أن يكون هذا DDD أو BB ؛ لذلك لا يصلح الخيار الأول
10) إذا كانت D = 01 ، تتطابق سلسلة الكود هذه مع بداية T = 011 ، فمن المستحيل فك تشفير السلسلة 011 بشكل لا لبس فيه: يمكن أن يكون YES أو T ؛ لذا فإن الخيار الثاني غير مناسب أيضًا
11) إذا كانت D = 11 ، فإن حالة Fano منتهكة أيضًا: تتطابق كلمة الشفرة A = 1 مع بداية شفرة الحرف D ، فمن المستحيل فك تشفير السلسلة 111 بشكل لا لبس فيه: يمكن لهذا أن يكون YES أو AAA ؛ الخيار الثالث لا يصلح
12) للخيار الرابع ، D = 010 ، لم يتم انتهاك حالة Fano ؛
13) الإجابة الصحيحة هي 4.

2. من أجل نقل عبر قناة اتصال لرسالة تتكون فقط من الأحرف A ، B ، C ، D ، قرروا استخدام رمز غير متساوٍ في الطول: A = 0 ، B = 10 ، C = 110. كيف ينبغي تشفير الحرف G بحيث يكون طول الشفرة ضئيلاً ويُسمح بتجزئة الرسائل المشفرة؟
1) 1 2) 1110 3) 111 4) 11
الحل (الخيار 1 ، طريقة الاختيار):
1) النظر في جميع الخيارات من أجل زيادة طول حرف الرمز G.
2) نبدأ بـ T = 1 ؛ اتضح أن الرسالة "10" يمكن فك شفرتها بطريقتين: مثل GA أو B ، لذا فإن هذا الخيار غير مناسب
3) الخيار الأطول التالي هو T = 11؛ في هذه الحالة ، يمكن فك ترميز الرسالة "110" على أنها HA أو B ، لذا فإن هذا الخيار غير مناسب أيضًا
4) الخيار الثالث ، G = 111 ، يعطي فكًا لا لبس فيه في كل توليفات الحروف ، لذلك ...
5) ... الإجابة الصحيحة هي 3.

المشاكل المحتملة:
عند التكرار ، يمكنك ارتكاب خطأ و "عرض" أي خيار

الحل (الخيار 2 ، طريقة "ذكية"):
1) لكي يتم فك رموز رسالة مسجلة باستخدام شفرة غير موحدة بشكل لا لبس فيه ، يجب ألا يكون أي رمز بداية لشفرة أخرى (أطول) ؛ تسمى هذه الحالة حالة Fano
2) كما هو الحال في الحل الأول ، فإننا ننظر في الخيارات التي تبدأ بأقصر شفرة للحرف Γ ؛ في حالتنا ، رمز T = 1 هو بداية رموز الأحرف B و C ، لذلك لم يتم استيفاء حالة Fano ، لا يتناسب هذا الرمز
3) الرمز D = 11 هو أيضًا بداية رمز آخر (رمز الحرف B) ، وبالتالي ، يعد هذا أيضًا متغيرًا خاطئًا
4) البديل الثالث من الكود ، G = 111 ، ليس بداية أي كود معروف بالفعل ؛ بالإضافة إلى ذلك ، لا يوجد أي رمز موجود هو بداية الكود 111 ؛ حتى تتحقق حالة فانو
5) لذا فإن الإجابة الصحيحة هي 3.

تحميل مجاني الكتاب الإلكتروني في تنسيق مناسب وقراءة:

قم بتنزيل الاختبار على علوم الكمبيوتر ، مهمة A9 ، Polyakov K. - fileskachat.com ، تنزيل سريع ومجاني.