متى ولماذا نشأت نظرية الترميز. نظرية الترميز. أنواع الترميز. الترميز. مفاهيم أساسية

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

صيغة

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

برنامج الدورة

1. الترميز الأبجدي. شروط كافية لفك تشفير لا لبس فيه: التوحيد ، البادئة ، اللاحقة. الاعتراف بالتفرد: معيار ماركوف. تقدير لطول كلمة غامضة فك التشفير.
2. عدم المساواة بين كرافت وماكميلان ؛ وجود رمز بادئة مع مجموعة معينة من أطوال الكلمات ؛ نتيجة طبيعية لعالمية رموز البادئة.
3. رموز الحد الأدنى من التكرار: بيان المشكلة ، نظرية تخفيض هوفمان.
4. مهمة تصحيح وكشف الأخطاء. تفسير هندسي. أنواع الخطأ. مقاييس هامنج و ليفنشتاين. مسافة الرمز. المهام الرئيسية لنظرية أكواد تصحيح الخطأ.
5. رموز فارشاموف - تينينجولتس ، خوارزميات لتصحيح أخطاء فردية من إسقاط وإدخال الرموز.
6. أبسط حدود لمعلمات رموز تصحيح أخطاء الاستبدال: حدود التعبئة الكروية ، وحدود Singleton ، وحدود Plotkin.
7. تضمين المساحات المترية. Lemma على عدد النواقل في الفضاء الإقليدي. حدود الياس - باساليغو.
8. رموز الخط. تعريفات. توليد وفحص المصفوفات. العلاقة بين مسافة الرمز والتحقق من المصفوفة. حدود فارشاموف - جيلبرت. الترميز المنهجي. متلازمة فك. رموز هامينج.
9. الكود المتبقي. حدود غريسمر - سليمان - ستيفلر.
10. تعقيد مشكلة فك الشفرات الخطية: مشكلة NCP (مشكلة حول أقرب كلمة مشفرة).
11. رموز ريد سليمان. خوارزمية فك تشفير Berlekamp-Welch.
12. أكواد ريد-مولر: مسافة الشفرة ، خوارزمية الغالبية.
13. متغيرات التعميمات لبناء ريد مولر. ليما ليبتون-ديميلو-شوارتز-زيبل. مفهوم الرموز الجبرية.
14. موسع الرسوم البيانية. دليل احتمالي لوجود الموسعات. أكواد تستند إلى الرسوم البيانية ثنائية الأجزاء. رمز مسافة الرموز على أساس الموسعات. خوارزمية فك التشفير Sipser-Spielman.
15. نظريات شانون لنموذج القناة الاحتمالية.
16. تطبيقات كود تصحيح الخطأ. بروتوكول عشوائي في تعقيد الاتصالات. التشفير McEliece. مجموعات متجانسة (عشوائية زائفة) تعتمد على الرموز وتطبيقاتها لإزالة العشوائية في مشكلة MAX-SAT.

من ويكيبيديا، الموسوعة الحرة

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

معلومات عامة

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

ضغط البيانات

تصحيح الخطأ المرسل

التشفير

التشفير (من اليونانية الأخرى. κρυπτός - مخفي و γράφω - أكتب) ، هذا هو مجال المعرفة حول طرق ضمان السرية (استحالة قراءة المعلومات للغرباء) ، وسلامة البيانات (استحالة تغيير المعلومات بشكل غير محسوس) ، والمصادقة (مصادقة التأليف أو خصائص أخرى للكائن) ، وكذلك استحالة رفض التأليف

04/04/2006 ليونيد تشيرناك التصنيف: تكنولوجيا

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

"الأنظمة المفتوحة"

كان من المستحيل إنشاء أجهزة كمبيوتر إذا لم يتم إنشاء نظرية تشفير الإشارة في وقت واحد مع مظهرها.

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

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

تم اقتراح الحل النظري الأول لمشكلة نقل البيانات عبر القنوات الصاخبة من قبل كلود شانون ، مؤسس نظرية المعلومات الإحصائية. كان شانون نجمًا في عصره ، وكان أحد نخبة الأكاديميين الأمريكيين. كطالب دراسات عليا في فانيفار بوش ، في عام 1940 حصل على جائزة نوبل (يجب عدم الخلط بينه وبين جائزة نوبل!) ، مُنحت للعلماء الذين تقل أعمارهم عن 30 عامًا. أثناء وجوده في Bell Labs ، كتب شانون "نظرية رياضية لنقل الرسائل" (1948) ، حيث أوضح أنه إذا كان عرض النطاق الترددي للقناة أكبر من إنتروبيا مصدر الرسالة ، فيمكن حينئذٍ تشفير الرسالة بحيث تكون تنتقل دون تأخير لا داعي له. تم تضمين هذا الاستنتاج في إحدى النظريات التي أثبتتها شانون ، ويتلخص معناها في حقيقة أنه إذا كانت هناك قناة ذات عرض نطاق كافٍ ، فيمكن إرسال رسالة مع بعض التأخير الزمني. بالإضافة إلى ذلك ، أظهر الإمكانية النظرية للإرسال الموثوق به في ظل وجود ضوضاء في القناة. تمت مقارنة الصيغة C = W log ((P + N) / N) ، المنحوتة على نصب تذكاري متواضع لشانون ، مثبتة في مسقط رأسه في ميشيغان ، من حيث القيمة مع صيغة ألبرت أينشتاين E = mc 2.

أدى عمل شانون إلى مزيد من البحث في مجال نظرية المعلومات ، لكن لم يكن لديهم تطبيق هندسي عملي. أصبح الانتقال من النظرية إلى التطبيق ممكنًا بفضل جهود ريتشارد هامينج ، زميل شانون في مختبرات بيل ، الذي اكتسب شهرة لاكتشافه فئة من الأكواد أطلق عليها اسم "أكواد هامينج". هناك أسطورة مفادها أن الإزعاج من العمل بالبطاقات المثقوبة على آلة حساب التتابع Bell Model V في منتصف الأربعينيات من القرن الماضي دفع إلى اختراع أكواد Hamming الخاصة بهم. لقد مُنح وقتًا للعمل على الجهاز في عطلات نهاية الأسبوع عندما لم يكن هناك مشغلون ، وكان عليه هو نفسه العبث بالمدخلات. كن على هذا النحو ، لكن تقويض الرموز المقترحة قادرة على تصحيح الأخطاء في قنوات الاتصال ، بما في ذلك خطوط نقل البيانات في أجهزة الكمبيوتر ، في المقام الأول بين المعالج والذاكرة. أصبحت رموز هامنج دليلاً على كيفية تحقيق الاحتمالات التي أشارت إليها نظريات شانون في الممارسة العملية.

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

من المؤكد فقط أن هامنج هو أول من اقترح "أكواد تصحيح الأخطاء" (كود تصحيح الخطأ ، ECC). يتم استخدام التعديلات الحديثة لهذه الأكواد في جميع أنظمة تخزين البيانات وللتبادل بين المعالج وذاكرة الوصول العشوائي. أحد المتغيرات الخاصة بهم ، أكواد Reed-Solomon ، تُستخدم في الأقراص المدمجة ، مما يسمح بتشغيل التسجيلات دون صرير أو ضوضاء يمكن أن تسبب خدوشًا وجزيئات الغبار. هناك العديد من إصدارات الأكواد المبنية على Hamming ، فهي تختلف في خوارزميات الترميز وعدد بتات الفحص. اكتسبت هذه الرموز أهمية خاصة فيما يتعلق بتطوير اتصالات الفضاء السحيق مع المحطات بين الكواكب ، على سبيل المثال ، هناك رموز Reed-Muller ، حيث يوجد 32 بت تحكم لسبع بتات معلومات ، أو 26 بتة لستة.

من بين أحدث رموز ECC ، يجب ذكر أكواد LDPC (كود فحص التماثل منخفض الكثافة). في الواقع ، لقد عُرفوا منذ حوالي ثلاثين عامًا ، ولكن تم اكتشاف اهتمام خاص بهم على وجه التحديد في السنوات الأخيرة ، عندما بدأ التلفزيون عالي الوضوح في التطور. رموز LDPC ليست موثوقة بنسبة 100٪ ، ولكن يمكن تعديل معدل الخطأ إلى المستوى المطلوب ، مع الاستفادة من عرض النطاق الترددي للقناة إلى الحد الأقصى. "أكواد Turbo" قريبة منهم ، فهي فعالة عند العمل مع الكائنات الموجودة في الفضاء السحيق وبعرض نطاق محدود للقناة.

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

تم استدعاء هذه النظرية بشكل مختلف ، بما في ذلك "نظرية WKS" (الاختصار WKS مأخوذ من ويتاكر ، كوتيلنيكوف ، شانون). في بعض المصادر ، يتم استخدام كل من نظرية أخذ العينات Nyquist-Shannon ونظرية أخذ العينات Whittaker-Shannon ، وفي الكتب المدرسية الجامعية المحلية ، يتم العثور على "نظرية Kotelnikov" في أغلب الأحيان. في الواقع ، للنظرية تاريخ أطول. تم إثبات الجزء الأول منه في عام 1897 من قبل عالم الرياضيات الفرنسي إميل بوريل. ساهم إدموند ويتاكر عام 1915. في عام 1920 ، نشر الياباني كينوسوكي أوغورا تصحيحات لأبحاث ويتاكر ، وفي عام 1928 صقل الأمريكي هاري نيكويست مبادئ الرقمنة وإعادة بناء الإشارات التناظرية.

كلود شانون(1916 - 2001) من سنوات دراسته أظهر اهتمامًا متساويًا بالرياضيات والهندسة الكهربائية. في عام 1932 ، التحق بجامعة ميشيغان ، في عام 1936 - في معهد ماساتشوستس للتكنولوجيا ، وتخرج منه عام 1940 ، وحصل على درجتين - ماجستير في الهندسة الكهربائية ودكتوراه في الرياضيات. في عام 1941 ، انضم شانون إلى مختبرات بيل. هنا بدأ في تطوير الأفكار التي أدت لاحقًا إلى نظرية المعلومات. في عام 1948 ، نشر شانون مقالاً بعنوان "نظرية الاتصال الرياضية" ، حيث تمت صياغة الأفكار الأساسية للعالم ، ولا سيما تحديد كمية المعلومات من خلال الانتروبيا ، واقترح أيضًا وحدة المعلومات التي تحدد اختيار اثنين خيارات محتملة متساوية ، أي ما تم تسميته لاحقًا قليلاً. في 1957-1961 ، نشر شانون أعمالًا أثبتت نظرية الإنتاجية لقنوات الاتصال الصاخبة ، والتي تحمل اسمه الآن. في عام 1957 ، أصبح شانون أستاذًا في معهد ماساتشوستس للتكنولوجيا ، حيث تقاعد بعد 21 عامًا. في "راحة مستحقة" كرس شانون نفسه تمامًا لشغفه القديم بألعاب الخفة. قام ببناء العديد من آلات الشعوذة حتى أنه ابتكر نظرية عامة عن ألعاب الخفة.

ريتشارد هامينج(1915 - 1998) بدأ تعليمه في جامعة شيكاغو حيث حصل على درجة البكالوريوس عام 1937. في عام 1939 حصل على درجة الماجستير من جامعة نبراسكا ودكتوراه في الرياضيات من جامعة إلينوي. في عام 1945 ، بدأ هامينغ العمل في مشروع مانهاتن ، وهو جهد بحثي حكومي ضخم لبناء القنبلة الذرية. في عام 1946 ، انضم هامينغ إلى معامل بيل للهاتف ، حيث عمل مع كلود شانون. في عام 1976 ، حصل هامينغ على كرسي في المدرسة البحرية للدراسات العليا في مونتيري ، كاليفورنيا.

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

فلاديمير كوتيلنيكوف(1908-2005) في عام 1926 التحق بقسم الهندسة الكهربائية في مدرسة موسكو التقنية العليا التي تحمل اسم NE Bauman (MVTU) ، لكنه أصبح خريجًا من معهد موسكو لهندسة الطاقة (MPEI) ، والذي انفصل عن MVTU كمعهد مستقل . أثناء دراسته في المدرسة العليا (1931-1933) ، صاغ Kotelnikov رياضيًا بدقة وأثبت "نظرية المرجع" ، التي سُميت لاحقًا باسمه. بعد تخرجه من المدرسة العليا في عام 1933 ، ذهب كوتيلنيكوف ، الذي ظل يدرس في معهد موسكو لهندسة الطاقة ، للعمل في المعهد المركزي لبحوث الاتصالات (TsNIIS). في عام 1941 ، صاغ V. في عام 1944 ، تولى Kotelnikov منصب الأستاذ ، وعميد كلية الهندسة اللاسلكية في MPEI ، حيث عمل حتى عام 1980. في عام 1953 ، في سن 45 ، تم انتخاب Kotelnikov على الفور عضوا كامل العضوية في أكاديمية العلوم في اتحاد الجمهوريات الاشتراكية السوفياتية. Kotelnikov من عام 1968 إلى عام 1990 كان أيضًا أستاذًا ورئيس قسم في معهد موسكو للفيزياء والتكنولوجيا.

ولادة نظرية الترميز

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

الموضوع 5.2. الترميز الأبجدي في الحالة العامة ، يمكن تمثيل مشكلة الترميز على النحو التالي. دعنا نحدد حرفين أبجديين A و B ، يتكونان من عدد محدود من الأحرف: و. تسمى عناصر الأبجدية بالحروف. المجموعة المرتبة في الأبجدية A ستسمى كلمة ، حيث n = l () = | |. ، يُظهر الرقم n عدد الأحرف في الكلمة ويسمى طول الكلمة ، ويُرمز إلى الكلمة الفارغة: بالنسبة للكلمة ، الحرف a1 ، يُطلق عليه بداية الكلمة ، أو البادئة ، الحرف a هي نهاية الكلمة أو postfix. ، والكلمات يمكن دمجها. للقيام بذلك ، يجب أن تتبع بادئة الكلمة الثانية مباشرةً بعد الإصلاح الأول ، بينما في الكلمة الجديدة يفقدون حالتهم بشكل طبيعي ، ما لم تكن إحدى الكلمات فارغة. مركب الكلمات ويشار إليه ، علاوة على ذلك ، يتم الإشارة إلى مركب n من الكلمات المتطابقة. يتم الإشارة إلى مجموعة جميع الكلمات غير الفارغة من الأبجدية A بالرمز A *: تسمى المجموعة A الأبجدية للرسالة ، وتسمى المجموعة B الأبجدية الترميزية. سيتم الإشارة إلى مجموعة الكلمات المكونة في الأبجدية B بالرمز B *.

قم بالإشارة بواسطة F إلى تعيين الكلمات من الأبجدية A إلى الأبجدية B. ثم تسمى الكلمة رمز الكلمة. الترميز هو طريقة عالمية لعرض المعلومات أثناء تخزينها ونقلها ومعالجتها في شكل نظام من المراسلات بين عناصر الرسالة والإشارات التي يمكن من خلالها إصلاح هذه العناصر. وبالتالي ، فإن الكود هو قاعدة للتحويل الواضح (أي الوظيفة) لرسالة من نموذج تمثيل رمزي (الأبجدية الأصلية أ) إلى آخر (أبجدية الكائن ب) ، عادةً دون فقدان أي معلومات. تسمى عملية تحويل كلمات الأبجدية الأصلية A إلى الأبجدية B من F: A * B * ترميز المعلومات. تسمى عملية تحويل الكلمة مرة أخرى فك التشفير. وبالتالي ، فإن فك التشفير هو معكوس F ، أي F1. في كلمة واحدة نظرًا لأنه يجب إجراء عملية فك تشفير لأي تشفير ، يجب أن يكون التعيين قابلاً للانعكاس (انحراف). إذا كان | B | = m ، فإن F تسمى تشفير المحاكاة ، والحالة الأكثر شيوعًا هي B = (0 ، 1) التشفير الثنائي. هذه هي الحالة التي يتم النظر فيها أدناه. إذا كانت كل كلمات الشفرة لها نفس الطول ، فإن الكود يسمى موحد أو كتلة. يمكن تحديد الترميز الأبجدي (أو حرفًا بحرف) بواسطة جدول الرموز. سيكون بعض الاستبدال بمثابة رمز أو وظيفة تشفير. ثم أين. يُشار إلى هذا الترميز حرفًا بحرف على أنه مجموعة من الرموز الأولية. يمكن استخدام الترميز الأبجدي لأي مجموعة من الرسائل. وبالتالي ، فإن الترميز الأبجدي هو الأبسط ويمكن إدخاله دائمًا في أبجديات غير فارغة. . العديد من رموز الحروف

مثال: دع الحروف الهجائية A = (0 ، 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8 ، 9) ب = (0 ، 1) يتم ذكرها. ثم يمكن أن يكون جدول الترميز بديلا:. هذا هو ترميز BCD ، وهو واحد لواحد وبالتالي يمكن فك تشفيره. ومع ذلك ، فإن المخطط ليس واحد لواحد. على سبيل المثال ، يمكن أن تتطابق المجموعة المكونة من ستة أحرف 111111 مع كل من الكلمة 333 و 77 ، بالإضافة إلى 111111 أو 137 أو 3311 أو 7111 بالإضافة إلى أي تبديل. يسمى مخطط الترميز الأبجدي البادئة إذا لم يكن الرمز الأولي لحرف ما هو البادئة للرمز الأولي لحرف آخر. يقال إن مخطط الترميز الأبجدي قابل للفصل إذا تحللت أي كلمة مكونة من رموز أولية إلى أكواد أولية بطريقة فريدة. يسمح الترميز الأبجدي بنظام قابل للفصل بفك التشفير. يمكن إثبات أن مخطط البادئة قابل للفصل. لكي يكون مخطط التشفير الأبجدي قابلاً للفصل ، يجب أن تفي أطوال الرموز الأولية بعلاقة تعرف باسم عدم مساواة ماكميلان. عدم مساواة ماكميلان إذا كان مخطط الترميز الأبجدي

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

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

حيث pi هو احتمال ظهور الحرف ai ، ويتم استبعاد الأحرف التي لا يوجد احتمال لظهورها في الرسالة ويتم ترتيب الأحرف بترتيب تنازلي لاحتمال ظهور رسالة حدوثها ، والتي تم تحديدها وتعريفها على أنها مثال. بالنسبة لنظام التشفير الأبجدي القابل للفصل A = (أ ، ب) ، ب = (0،1) ، في ظل التوزيع الاحتمالي ، تكون تكلفة التشفير ، وتحت التوزيع الاحتمالي ، تكلفة التشفير هي

الموضوع 5.4. تشفير هوفمان اخترع ديفيد هوفمان هذه الخوارزمية في عام 1952. الموضوع 5.5. الترميز الحسابي كما في خوارزمية هوفمان ، كل شيء يبدأ بجدول العناصر والاحتمالات المقابلة. لنفترض أن الأبجدية المدخلة تتكون من ثلاثة عناصر فقط: a1 و a2 و a3 ، وفي نفس الوقت P (a1) = 1/2 P (a2) = 1/3 P (a3) ​​= 1/6 افترض أيضًا أننا بحاجة لتشفير التسلسل a1، a1، a2، a3. دعونا نقسم الفترة الزمنية ، حيث p هي عدد ثابت ، 0<р<(r­1)/2r, а "мощностная" граница где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист

ra تحول وعنصر أغلبية واحد وتصحيح خطأ واحد ، له أمر (قارن مع (2)). كرياضيات عادة ما يتم النظر في نماذج التشفير وفك التشفير من دائرة العناصر الوظيفية ويُفهم التعقيد على أنه عدد العناصر في الدائرة. بالنسبة للفئات المعروفة من أكواد تصحيح الأخطاء ، تم إجراء دراسة للخوارزميات الممكنة لـ K. و D. وتم الحصول على حدود عليا على مدى تعقيد المشفر ومفكك التشفير. تم العثور على بعض العلاقات أيضًا بين معدل التشفير ، ومناعة الضوضاء للتشفير ، وتعقيد وحدة فك التشفير (انظر). هناك اتجاه آخر للبحث في نظرية الترميز مرتبط بحقيقة أن العديد من النتائج (على سبيل المثال ، نظرية شانون والربط (3)) ليست "بناءة" ، ولكنها نظريات حول وجود متواليات لانهائية من أكواد (كن). في هذا فيما يتعلق ، تُبذل جهود لإثبات هذه النتائج في فئة مثل هذه التسلسلات من أكواد (Kn) ، فبالنسبة لـ kp ، توجد آلة تورينج تدرك أن كلمة تعسفية ذات طول l تنتمي إلى مجموعة زمنية ذات وقت بطيء ترتيب النمو فيما يتعلق l (على سبيل المثال ، llog l). أدت بعض الإنشاءات والأساليب الجديدة لاشتقاق الحدود التي تم تطويرها في نظرية التشفير إلى تقدم كبير في الأسئلة التي تبدو للوهلة الأولى بعيدة جدًا عن المشكلات التقليدية لنظرية الترميز. هنا يجب أن نشير إلى استخدام الحد الأقصى للشفرة مع تصحيح خطأ واحد في الطريقة المثلى للأعراض لتحقيق وظائف جبر المنطق بواسطة دارات التلامس ؛ التحسين الأساسي للحد الأعلى لكثافة التعبئة لـ إعادة أبعاد الفضاء الإقليدي بكرات متساوية ؛ حول استخدام عدم المساواة (1) في تقدير مدى تعقيد التنفيذ بواسطة الصيغ لفئة واحدة من وظائف جبر المنطق. تجد أفكار ونتائج نظرية التشفير مزيدًا من التطور في مشاكل توليف دوائر التصحيح الذاتي والدوائر الموثوقة من عناصر غير موثوقة. مضاء: شانون ك. ، يعمل على نظرية المعلومات وعلم التحكم الآلي ، العابرة. من الإنجليزية ، M. ، 1963 ؛ Berlekamp E. ، نظرية الترميز الجبري ، العابرة. من الإنجليزية ، M. ، 1971 ؛ بيترسون ، دبليو ، ويلدون ، إي. ، رموز تصحيح الأخطاء ، العابرة. من الإنجليزية ، الطبعة الثانية ، M. ، 1976 ؛ الرياضيات المنفصلة والأسئلة الرياضية لعلم التحكم الآلي ، المجلد 1 ، M. ، 1974 ، القسم 5 ؛ Bassalygo L.A، Zyablov V.، Pinsker M. S.، "Problems of information Transmission"، 1977، vol. 13، No. 3، p. 517 ؛ [في] في إم سيدلنيكوف ، "مات. السبت" ، 1974 ، ضد 95 ، إ. 1 ، ص. 148 58. في آي ليفينشتاين.

الموسوعة الرياضية. - م: الموسوعة السوفيتية. آي إم فينوغرادوف. 1977-1985.  الترميز الأبجدي  فضاء كوكليدان انظر أيضًا في القواميس الأخرى: فك التشفير - انظر الترميز وفك التشفير ... موسوعة الرياضيات  ترميز الصوت - يجب نشر هذه المقالة. من فضلك ، قم بتنسيقه وفقًا لقواعد تنسيق المقالات. أساس تشفير الصوت باستخدام جهاز الكمبيوتر هو عملية تحويل اهتزازات الهواء إلى اهتزازات كهربائية ... صور كود ويكيبيديا) ، والتي يتم إجراؤها وفقًا للتعريف. القواعد ، مجموع k ryh naz. cipher K.، ... ... الموسوعة الفلسفية  ترميز المعلومات - إنشاء مراسلات بين عناصر الرسالة والإشارات ، والتي يمكن من خلالها إصلاح هذه العناصر. لنفترض أن B عبارة عن مجموعة من عناصر الرسالة ، وأبجدية بها رموز ، ولندع سلسلة محدودة من الرموز. باختصار ... ... الموسوعة المادية  الترميز الأمثل - (في علم النفس الهندسي) (الترميز الهندسي الأمثل) إنشاء أكواد تضمن أقصى سرعة وموثوقية لتلقي ومعالجة المعلومات حول كائن يتحكم فيه عامل بشري (انظر استقبال المعلومات ، فك التشفير). مشكلة K. o. ...... موسوعة نفسية كبيرة  فك الشفرة (في علم النفس الهندسي) - (فك ترميز اللغة الإنجليزية) العملية النهائية لعملية تلقي المعلومات من قبل عامل بشري ، والتي تتكون من إعادة تشفير المعلمات التي تميز الخصائص حالة كائن التحكم ، وترجمتها إلى صورة الكائن المتحكم فيه (انظر الترميز ... ... موسوعة نفسية كبيرة

 فك التشفير - استعادة رسالة مشفرة بالإشارات المرسلة والمستقبلة (انظر الترميز) ... قاموس الاقتصاد والرياضيات  الترميز - الترميز. إحدى مراحل توليد الكلام ، في حين أن "فك التشفير" هو الاستقبال والتفسير ، عملية فهم رسالة الكلام. انظر علم اللغة النفسي ... قاموس جديد للمصطلحات والمفاهيم المنهجية (نظرية وممارسة تدريس اللغات)  البرمجة - (ترميز اللغة الإنجليزية). 1. تحويل إشارة من شكل طاقة إلى آخر 2. تحويل نظام إشارات أو إشارات إلى أخرى ، وهو ما يسمى أيضًا "تحويل الشفرة" ، "تغيير الشفرة" (للكلام ، "الترجمة"). 3. K. (ذاكري) ... ... موسوعة نفسية كبيرة  فك التشفير - تتناول هذه المقالة الكود في نظرية المعلومات ، لمعرفة المعاني الأخرى لهذه الكلمة ، انظر الكود (توضيح). الكود هو قاعدة (خوارزمية) لمطابقة كل رسالة محددة بمجموعة محددة بدقة من الرموز (الأحرف) (أو الإشارات). يُطلق عليه أيضًا رمز ... ... التشفير الأمثل يمكن تشفير نفس الرسالة بطرق مختلفة. الرمز المشفر على النحو الأمثل هو الرمز الذي يتم فيه إنفاق الحد الأدنى من الوقت على إرسال الرسائل. إذا كان إرسال كل حرف أولي (0 أو 1) يستغرق نفس الوقت ، فسيكون الرمز الأمثل هو الرمز الذي سيكون له أقل طول ممكن. مثال 1. لنفترض أن هناك متغير عشوائي X (x1 ، x2 ، x3 ، x4 ، x5 ، x6 ، x7 ، x8) به ثماني حالات مع توزيع احتمالي لتشفير أبجدية من ثمانية أحرف برمز ثنائي موحد ، نحتاج إلى ثلاثة الأحرف: هذا 000 ، 001 ، 010 ، 011 ، 100 ، 101 ، 110 ، 111 للإجابة عما إذا كان هذا الرمز جيدًا أم لا ، تحتاج إلى مقارنته بالقيمة المثلى ، أي تحديد الانتروبيا

بعد تحديد التكرار L بالصيغة L = 1H / H0 = 12.75 / 3 = 0.084 ، نرى أنه من الممكن تقليل طول الكود بنسبة 8.4٪. السؤال الذي يطرح نفسه: هل من الممكن تكوين رمز يكون فيه ، في المتوسط ​​، عددًا أقل من الأحرف الأولية لكل حرف. هذه الرموز موجودة. هذه هي شفرات ShannonFano و Huffman. مبدأ تكوين الكود الأمثل: 1. يجب أن يحمل كل حرف ابتدائي أكبر قدر من المعلومات ، لذلك من الضروري أن تتكرر الأحرف الأولية (0 و 1) في النص المشفر في المتوسط ​​بشكل متساوٍ. سيكون الانتروبيا في هذه الحالة هو الحد الأقصى. 2. من الضروري أن يتم تخصيص كلمات رمزية أقصر من الأبجدية الثانوية لأحرف الأبجدية الأولية ، والتي لها احتمالية أعلى.

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

علاوة على ذلك ، نفترض أن مصدر المعلومات منفصل ، ويعطي سلسلة من الرسائل الأولية (i ،) ، يتم اختيار كل منها من مجموعة منفصلة (الأبجدية) a ، a 2 ، ... ، d A ؛ لهو حجم الأبجدية لمصدر المعلومات.

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

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

تيم أن ^ ص (أ:) = 1 ، لأنني جميعًا أقوم بتشكيل مجموعة كاملة من الأحداث

gyi) ، ويتم اختيار هذه الرموز باستخدام بعض التبعية الوظيفية ي (أ ،)= P (a،) = 1 ، إذا كان اختيار الرمز من قبل المصدر محددًا مسبقًا ، ي (أ ،)= أ "أ P (a t، a)- احتمال مثل هذا الاختيار ، فإن كمية المعلومات الواردة في زوج من الرموز تساوي مجموع كمية المعلومات الواردة في كل من الرموز i و i. تسمى هذه الخاصية الخاصة بالقياس الكمي للمعلومات الإضافية .

نحن نصدق ذلك ف (أ ،)- الاحتمال الشرطي لاختيار الحرف i بعد كل الأحرف التي تسبقه ف (ا ،، i ،) هو الاحتمال الشرطي لاختيار الرمز i ؛ بعد أنا وكل ما سبقه ، ولكن بالنظر إلى ذلك الفوسفور (أ 1 ، أ 1) \ u003d ف (أ) P (i، | i y) ، يمكن كتابة شرط الجمع

نقدم التدوين ف (أ) = ف ص ف (ع) \ u003d سوإعادة كتابة الشرط (5.1):

نحن نصدق ذلك R ، O* 0. باستخدام التعبير (5.2) نحدد شكل الدالة (р (ص).عن طريق التفريق والضرب في ص * 0 والدلالة RO = R ،اكتب

لاحظ أن العلاقة (5.3) راضية عن أي R و O u ^^ O. ومع ذلك ، فإن هذا المطلب يؤدي إلى ثبات الجانبين الأيمن والأيسر لـ (5.3): Pq> "(P) = Ar "(/؟) - ل -مقدار ثابت. ثم نأتي إلى المعادلة كمبيوتر> "(P) = لوبعد الاندماج نحصل عليه

لنأخذ في الاعتبار أننا سنعيد كتابته

وبالتالي ، في ظل استيفاء شرطين على خصائص J (a ،) ، اتضح أن شكل الاعتماد الوظيفي ي (أ ،)حول احتمال اختيار رمز فيحتى معامل ثابت لبشكل فريد

معامل في الرياضيات او درجة ليؤثر فقط على المقياس ويحدد نظام الوحدات لقياس كمية المعلومات. منذ ln [P] F 0 ، فمن المنطقي أن تختار إلى نظام التشغيل بحيث يكون مقياسًا لمقدار المعلومات ي (أ)كان إيجابيا.

بعد أن قبلت ك =-1 ، اكتب

ويترتب على ذلك أن وحدة مقدار المعلومات تساوي المعلومات التي حدث بها حدث ، واحتمالية حدوثها تساوي أنا.تسمى هذه الوحدة من كمية المعلومات بالوحدة الطبيعية. غالبا ما يفترض أن ل= - إذن

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

حيث يمكن أن يكون اللوغاريتم بقاعدة عشوائية.

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

لا يعطي المقياس الكمي للمعلومات الواردة في الرسالة الأولية أ (، فكرة عن متوسط ​​كمية المعلومات J (أ) صادر عن المصدر عند تحديد رسالة أولية واحدة ميلادي

يميز متوسط ​​كمية المعلومات مصدر المعلومات ككل وهو أحد أهم خصائص أنظمة الاتصال.

دعونا نحدد هذه الخاصية لمصدر منفصل للرسائل المستقلة مع الأبجدية ل.للدلالة به على ال)متوسط ​​كمية المعلومات لكل حرف وهو التوقع الرياضي لمتغير عشوائي L - كمية المعلومات الموجودة في حرف تم اختياره عشوائيًا أ

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

ويترتب على التعبير (5.10) أنه إذا كان أحد الاحتمالات ف (أ)يساوي واحدًا (وبالتالي ، فإن كل الآخرين يساوي صفرًا) ، ثم تكون إنتروبيا مصدر المعلومات مساوية للصفر - فالرسالة محددة تمامًا.

سيكون الانتروبيا بحد أقصى إذا تساوت الاحتمالات السابقة لجميع الرموز الممكنة ل، بمعنى آخر. ص (أ () = 1 /ل،ومن بعد

إذا اختار المصدر بشكل مستقل الرموز الثنائية مع الاحتمالات P ، = ف (أ س)و P 2 \ u003d 1 - P ، فسيكون الانتروبيا لكل حرف

على التين. يوضح الشكل 16.1 اعتماد إنتروبيا المصدر الثنائي على الاحتمال المسبق للاختيار من بين رمزين ثنائيين ، ويوضح هذا الشكل أيضًا أن الانتروبيا هي الحد الأقصى عند R ، = ص 2 = 0,5

1 o 1 dvd - وفي الوحدات الثنائية log 2 2 = 1-

أرز. 5.1 الاعتماد على الانتروبيا في ك = 2 على احتمال اختيار واحد منهم

إنتروبيا للمصادر مع اختيار متكافئ للرموز ، ولكن بأحجام مختلفة من الحروف الهجائية ل،يزيد لوغاريتميًا مع النمو ل.

إذا كان احتمال اختيار الرموز مختلفًا ، فإن إنتروبيا المصدر تنخفض I ل)نسبة إلى الحد الأقصى الممكن H (A) psh =سجل ل.

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

من خلال تقديم الترميز P (aa ")من أجل الاحتمال الشرطي لاختيار الرمز أ ، (/ = 1, 2, ل)بافتراض أن الرمز قد تم اختياره مسبقًا أجيج =1,2,ل)وحذف التحولات نكتب بلا برهان

الذي يثبت عدم المساواة (5.13).

تتحقق المساواة في (5.13) أو (5.14) عندما

هذا يعني أن الاحتمال الشرطي لاختيار رمز ما يساوي الاحتمال غير المشروط لاختياره ، وهو أمر ممكن فقط للمصادر الخالية من الذاكرة.

ومن المثير للاهتمام أن إنتروبيا النص باللغة الروسية هي 1.5 وحدة ثنائية لكل حرف. في نفس الوقت ، مع نفس الأبجدية ك = 32 بشرط الرموز المستقلة والمتوازنة H (A) tp = 5 آحاد ثنائية لكل حرف. وبالتالي ، أدى وجود الروابط الداخلية إلى تقليل الانتروبيا بنحو 3.3 مرة.

من الخصائص المهمة للمصدر المنفصل التكرار p و:

التكرار في مصدر المعلومات هو كمية بلا أبعاد بداخلها. بطبيعة الحال ، في حالة عدم وجود فائض p u = 0.

لإرسال قدر معين من المعلومات من مصدر ليس له ارتباطات بين الرموز ، مع احتمالية متساوية لجميع الرموز ، والحد الأدنى لعدد الرموز المرسلة / 7 دقائق: / r 0 (/ 7 0 R (L max)) مطلوب. لإرسال نفس القدر من المعلومات من مصدر به إنتروبيا (الرموز مترابطة وغير محتملة بشكل غير متساوٍ) ، مطلوب متوسط ​​عدد الرموز n = n „H (A) m JH (A).

يتميز المصدر المنفصل أيضًا بالأداء ، والذي يتم تحديده بواسطة عدد الرموز لكل وحدة زمنية v H:

إذا كان الأداء I ل)حدد بالوحدات الثنائية ، والوقت بالثواني ، إذن على ال) -هو عدد الوحدات الثنائية في الثانية. بالنسبة للمصادر المنفصلة التي تنتج متواليات حروف ثابتة بطول كبير /؟ ص.كل التسلسلات النموذجية NlMl (A)المصدر في ص- »oo لها نفس احتمالية الحدوث تقريبًا

يميل إجمالي احتمال حدوث جميع التسلسلات غير النمطية إلى الصفر. وفقًا للمساواة (5.11) ، بافتراض أن احتمال تسلسل نموذجي / N rm (A) ،إنتروبيا المصدر هي logN TIin (، 4) ثم

ضع في اعتبارك مقدار وسرعة نقل المعلومات عبر قناة منفصلة بها ضوضاء. في السابق ، اعتبرنا المعلومات التي ينتجها مصدر منفصل في شكل سلسلة من الأحرف (أنا ،).

افترض الآن أن معلومات المصدر مشفرة وتمثل سلسلة من رموز الرموز (ب، (/ = 1,2، .. T -الشفرة الأساسية) ، متسقة مع قناة نقل المعلومات المنفصلة ، والتي يظهر عندها تسلسل من الرموز

نفترض أن عملية التشفير تتم واحد لواحد - من خلال تسلسل الأحرف (ب،)يمكن للمرء بشكل فريد استعادة التسلسل (i ،) ، أي من خلال رموز الكود ، من الممكن استعادة معلومات المصدر بالكامل.

ومع ذلك ، إذا اعتبرنا أحرف الهروب | ؟. j ورموز الإدخال (/> ،) ، إذن ، بسبب وجود تداخل في قناة إرسال المعلومات ، فإن الاستعادة مستحيلة. الانتروبيا لتسلسل الإخراج // (/؟)

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

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

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

رمز بجبنفس الرقم (/ = ي).ثم للحصول على قناة مثالية بدون ضوضاء ، نكتب:

بالرمز بج- ناتج القناة بسبب عدم المساواة (5.21)

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

ويحدد مقدار المعلومات المفقودة في القناة أثناء الإرسال.

تحديد قدم. وبمتوسط ​​(5.22) على جميع الرموز الممكنة ، نحصل على المجموع

الذي يحدد مقدار المعلومات المفقودة في القناة عند إرسال رمز أولي عبر قناة بدون ذاكرة عند تلقي رمز بج (ر).

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

أين P ^ bjbjj-الاحتمال المشترك لحدث ، عند إرساله

رمز ب.سوف يستغرق الرمز بر.

ح [ث /يعتمد على خصائص مصدر المعلومات على

إدخال القناة الخامسوعلى الخصائص الاحتمالية لقناة الاتصال. وفقًا لشانون في نظرية الاتصال الإحصائي ن (في / فييسمى عدم موثوقية القناة.

الانتروبيا الشرطية HB / ب، إنتروبيا من مصدر منفصل

في مدخلات القناة ح (ث)والنتروبيا و ^ ب) في إخراجها لا يمكن أن يكون

نفي. في قناة خالية من التداخل ، لا يمكن الاعتماد على القناة

ن (ت / ت = 0. طبقًا لـ (5.20) نلاحظ أن ح ^ ت / ت ^

والمساواة تحدث فقط عندما يكون مدخلات ومخرجات القناة مستقلة إحصائيًا:

لا تعتمد رموز الخرج على رموز الإدخال - حالة القناة المكسورة أو التداخل القوي للغاية.

كما في السابق ، بالنسبة للتسلسلات النموذجية ، يمكننا الكتابة

ليقول أنه في حالة عدم وجود تدخل ، لا يمكن الاعتماد عليها

تحت المعلومات المنقولة في المتوسط ​​عبر القناة J [ب / لكل رمز نفهم الفرق بين كمية المعلومات عند إدخال القناة ي (ب)والمعلومات المفقودة في /؟ القناة).

إذا كان مصدر المعلومات والقناة بلا ذاكرة ، إذن

يحدد التعبير (5.27) إنتروبيا رموز إخراج القناة. جزء من المعلومات عند خرج القناة مفيد ، والباقي خاطئ ، لأنه ناتج عن التداخل في القناة. دعونا نلاحظ ذلك ن [ت / 2؟) يعبر عن معلومات حول التداخل في القناة ، والفرق i (d) -I (d / d) - معلومات مفيدة مرت عبر القناة.

لاحظ أن الغالبية العظمى من التسلسلات المتكونة عند إخراج القناة غير نمطية ولها احتمالية إجمالية صغيرة جدًا.

كقاعدة عامة ، يتم أخذ النوع الأكثر شيوعًا من التداخل في الاعتبار - الضوضاء المضافة. N (ر) ؛الإشارة عند خرج القناة لها الشكل:

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

لأن و (^ ب/؟) و (ب) إذن ، وبالتالي ، فإن معلومات تسلسل الإخراج للقناة المنفصلة # (/) بالنسبة للإدخال ب (ر)أو العكس و (B) - H ^ in / in) (5).

بمعنى آخر ، لا يمكن أن تتجاوز المعلومات المرسلة عبر القناة المعلومات عند إدخالها.

إذا كان إدخال القناة يتلقى المتوسط س كفي ثانية واحدة ، من الممكن تحديد متوسط ​​معدل نقل المعلومات عبر قناة بها ضوضاء:

أين Н (В) = V ك J (ب ، ب ^ -أداء المصدر عند إدخال القناة ؛ n (in / in) \ u003d U to n (in، in) ~عدم موثوقية القناة لكل وحدة زمنية ؛ H (B) = V · K · H ^ B ^- أداء المصدر الناتج عن إخراج القناة (إعطاء جزء من المعلومات المفيدة وجزء من المعلومات الخاطئة) ؛ H ^ in / B ^ \ u003d U إلى 1 / (in / in)- مقدار المعلومات الخاطئة ،

خلق تداخلًا في القناة لكل وحدة زمنية.

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

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

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

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

بناءً على تعريف صبيب القناة المنفصلة ، نكتب

لاحظ أن C = 0 مع إدخال وإخراج مستقل (مستوى ضوضاء مرتفع في القناة) ، وبالتالي ،

في حالة عدم وجود تدخل تدخل على الإشارة.

لقناة متناظرة ثنائية بدون ذاكرة

أرز. 5.2

رسم بياني لاعتماد سعة القناة الثنائية على المعلمة صهو مبين في الشكل. 5.2 في ص= 1/2 قناة النطاق الترددي ج = 0 ، الانتروبيا الشرطية

// (/؟ //؟) = 1. فائدة عملية

يمثل الرسم البياني عند 0

ترتبط نظرية شانون الأساسية حول التشفير الأمثل بمفهوم السعة. صيغته لقناة منفصلة هي كما يلي: إذا كان أداء مصدر الرسالة على ال)أقل من عرض النطاق الترددي للقناة C:

هناك طريقة للتشفير وفك التشفير الأمثل ، والتي بموجبها يكون احتمال الخطأ أو عدم موثوقية القناة يمكن أن يكون n [a! A j صغيرًا بشكل تعسفي. إذا

لا توجد مثل هذه الطرق.

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

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

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