التكرار (نظرية المعلومات)

في نظرية المعلومات ، يقيس التكرار (الزيادة) الفرق النسبي بين إنتروبيا H(X) لمجموعة X ، وقيمتها القصوى الممكنة${\displaystyle \log(|{\mathcal {A}}_{X}|)}$[ ^{1 ] [ 2 ] بشكل غير رسمي، يُشير مصطلح} "المساحة" إلى مقدار "المساحة" المهدرة المستخدمة لنقل بيانات معينة. يُعد ضغط البيانات وسيلة لتقليل أو إزالة التكرار غير المرغوب فيه، بينما يُعد تصحيح الأخطاء الأمامي وسيلة لإضافة التكرار المطلوب لأغراض اكتشاف الأخطاء وتصحيحها عند الاتصال عبر قناة ذات ضوضاء عالية وسعة محدودة .

عند وصف تكرار البيانات الأولية، يُعرَّف معدل مصدر المعلومات بأنه متوسط ​​الإنتروبيا لكل رمز. بالنسبة للمصادر عديمة الذاكرة، يكون هذا مجرد إنتروبيا كل رمز، بينما في الحالة الأكثر عمومية لعملية عشوائية ، يكون

${\displaystyle r=\lim _{n\to \infty }{\frac {1}{n}}H(M_{1},M_{2},\dots M_{n}),}$

في النهاية، عندما يؤول n إلى اللانهاية، يكون معدل الإنتروبيا المشتركة لأول n رمزًا مقسومًا على n . من الشائع في نظرية المعلومات الحديث عن "معدل" أو " إنتروبيا " اللغة. وهذا مناسب، على سبيل المثال، عندما يكون مصدر المعلومات نثرًا إنجليزيًا. معدل مصدر عديم الذاكرة هو ببساطة${\displaystyle H(M)}$، لأنه بحكم التعريف لا يوجد ترابط بين الرسائل المتتالية لمصدر بلا ذاكرة.

المعدل المطلق للغة أو المصدر هو ببساطة

${\displaystyle R=\log |\mathbb {M} |,\,}$

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

ويمكن تعريف التكرار المطلق على النحو التالي:

${\displaystyle D=Rr,\,}$

الفرق بين المعدل المطلق والمعدل.

الكمية${\displaystyle {\frac {D}{R}}}$يُطلق عليها اسم التكرار النسبي ، وهي تُعطي أعلى نسبة ضغط بيانات ممكنة ، عند التعبير عنها كنسبة مئوية يُمكن بها تقليل حجم الملف. (عند التعبير عنها كنسبة بين حجم الملف الأصلي وحجم الملف المضغوط، فإن الكمية${\displaystyle R:r}$(يعطي أعلى نسبة ضغط يمكن تحقيقها). ويُكمّل مفهوم التكرار النسبي مفهوم الكفاءة ، الذي يُعرّف على النحو التالي:${\displaystyle {\frac {r}{R}},}$لهذا السبب.${\displaystyle {\frac {r}{R}}+{\frac {D}{R}}=1}$. المصدر الذي لا يحتوي على ذاكرة مع توزيع منتظم يكون لديه تكرار صفري (وبالتالي كفاءة 100٪)، ولا يمكن ضغطه.

يُعدّ معامل المعلومات المتبادلة أو المتغير المعياري مقياساً للتكرار بين متغيرين . أما معامل الارتباط الكلي فيُستخدم لقياس التكرار بين عدة متغيرات .

يشير تكرار البيانات المضغوطة إلى الفرق بين طول البيانات المضغوطة المتوقع${\displaystyle n}$رسائل${\displaystyle L(M^{n})\,\!}$(أو معدل البيانات المتوقع)${\displaystyle L(M^{n})/n\,\!}$) والإنتروبيا${\displaystyle nr\,\!}$(أو معدل الإنتروبيا)${\displaystyle r\,\!}$(نفترض هنا أن البيانات إرجودية وثابتة ، أي مصدر بلا ذاكرة). على الرغم من اختلاف المعدل${\displaystyle L(M^{n})/n-r\,\!}$يمكن أن تكون صغيرة بشكل تعسفي مثل${\displaystyle n\,\!}$ازداد الفرق الفعلي${\displaystyle L(M^{n})-nr\,\!}$، لا يمكن ذلك، على الرغم من أنه من الممكن نظريًا أن يكون محدودًا بـ 1 في حالة المصادر عديمة الذاكرة ذات الإنتروبيا المحدودة.

في سياق نظرية المعلومات، يمكن أن يشير التكرار أيضًا إلى المعلومات المتكررة بين معلومتين متبادلتين. على سبيل المثال، بالنظر إلى ثلاثة متغيرات${\displaystyle X_{1}}$،${\displaystyle X_{2}}$، و${\displaystyle Y}$من المعروف أن المعلومات المتبادلة المشتركة يمكن أن تكون أقل من مجموع المعلومات المتبادلة الهامشية:${\displaystyle I(X_{1},X_{2};Y)<I(X_{1};Y)+I(X_{2};Y)}$في هذه الحالة، على الأقل بعض المعلومات حول${\displaystyle Y}$تم الكشف عنها بواسطة${\displaystyle X_{1}}$أو${\displaystyle X_{2}}$هو نفسه. تُكمّل هذه الصياغة للتكرار مفهوم التآزر، الذي يحدث عندما تكون المعلومات المتبادلة المشتركة أكبر من مجموع المعلومات الهامشية، مما يشير إلى وجود معلومات لا يُكشف عنها إلا من خلال الحالة المشتركة وليس من خلال أي مجموعة أبسط من المصادر. ^{[ 3 ] [ 4 ]}

• ترميز الحد الأدنى من التكرار
  • ترميز هوفمان
• ضغط البيانات
• وظيفة هارتلي
• الإنتروبيا السالبة
• نظرية ترميز المصدر
• الإكمال الزائد

• رضا، فضل الله م. (1994) [1961]. مدخل إلى نظرية المعلومات . نيويورك: دوفر [ماكجرو هيل]. ISBN 0-486-68210-2.
• شناير، بروس (1996). التشفير التطبيقي: البروتوكولات والخوارزميات وشفرة المصدر بلغة سي . نيويورك: جون وايلي وأولاده، المحدودة. ISBN 0-471-12845-7.
• أوفارث، ب؛ لوبيز-سانشيز، م؛ سيركويدس، ج. (2010). "مقارنة مقاييس التكرار والملاءمة لاختيار الميزات في تصنيف الأنسجة في صور الأشعة المقطعية". التطورات في استخراج البيانات: التطبيقات والجوانب النظرية . سبرينغر. ص 248-262 . CiteSeerX 10.1.1.170.1528 .