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

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

وقد طور كود غولي الثنائي في عام 1949 . وهو كود تصحيح الخطأ القادر على تصحيح ما يصل إلى ثلاثة أخطاء في كل من الكلمة المكونه من 24 بت، وكشف الرابعة.

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

المقال الرئيسي: ضغط البيانات

والهدف من تكويد المصدر أن تحصل على بيانات المصدر وجعله أصغر.

التعريفات

و يمكن رؤية البيانات كمتغير عشوائي

${\displaystyle X:\Omega \rightarrow {\mathcal {X}}}$, عندما ${\displaystyle x\in {\mathcal {X}}}$ يظهر مع احتمال ${\displaystyle \mathbb {P} [X=x]}$.

يتم ترميز البيانات بواسطة سلاسل (كلمات) عبر الأبجدية ${\displaystyle \Sigma }$.

يعتبر الكود داله ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ (or ${\displaystyle \Sigma ^{+}}$ إذا كانت السلسلة الفارغة ليست جزءا من الأبجدية) ${\displaystyle C(x)}$ هي رمز الكلمة المرتبطه ب ${\displaystyle x}$.

طول رمز الكلمة مكتوب مثل

${\displaystyle l(C(x))}$.

الطول المتوقع للكود يكون

${\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]}$

تسلسل رموز الكلمة ${\displaystyle C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})}$.

كلمه الرمز للسلسلة الفارغة هي السلسلة الفارغة نفسها:

${\displaystyle C(\epsilon )=\epsilon }$

الخواص

• ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ هي ليست مفرده الطول لو المعادلة متوافقه
• ${\displaystyle C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}}$ هي كود فريد لو المعادلة متوافقه
• ${\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}}$ هي تتم بشكل فوري إذا ${\displaystyle C(x_{1})}$ ليس بادئه ${\displaystyle C(x_{2})}$ (والعكس بالعكس).

المبدأ

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

يسمى ضغط البيانات التي تحاول بشكل واضح للحد من متوسط طول الرسائل وفقا يسمى ضغط البيانات التي تحاول بشكل واضح للحد من متوسط طول الرسائل وفقا لاحتمال مفترض لنموذج معين هي تكويد العشوائيه.

التقنيات المختلفة المستخدمة من قبل مصدر أنظمة الترميز تحاول ان تحقق الحد الأقصى من العشوائيه للمصدر. C(x) ≥ H(x), عندما H(x) هو المصدر (معدل بت) و C(x) هو معدل البت بعد الضغط. على وجه الخصوص، لا يمكن لنظام مصدر الترميز أن يكون أفضل من العشوائيه للمصدر.

أمثله

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

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

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

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

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

المقال الرئيسي: الرمز الخطي

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

ينقسم نظرية الترميز الجبرية في الأساس إلى نوعين رئيسيين من أكواد:

1. أكواد الكتلة الخطية
2. أكواد التلافيف

كما تحلل الخصائص الثلاثة التالية للكود - أهمها:

1. طول كلمة الكود.
2. العدد الكلي لكلمات الكود السليم.
3. الحد الأدنى للمسافة بين كلمتين الكود السليم، وذلك باستخدام أساسا مسافه الهامنج، وأحيانا أيضا المسافات الأخرى مثل مسافة لي.

أكواد الكتلة الخطية

المقال الرئيسي: كتلة الكود

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

وتتلخص أكواد الكتلة الخطية من الحروف الهجائية على كود (على سبيل المثال، ثنائي أو ثلاثي) والمعايير (n,m,d_min)

1. n هو طول الكلمة المشفره في الرموز،
2. m هو عدد من مصدر الرموز التي سيتم استخدامها لترميز دفعة واحدة،
3. d_min هو الحد الأدنى للمسافة هامنج للكود.

وهناك أنواع عديدة من أكواد الكتلة الخطية، مثل:

1. رموز دوري (على سبيل المثال، رموز هامنج)
2. رموز التكرار
3. رموز التكافؤ
4. رموز كثيرات الحدود (على سبيل المثال، رموز كود بي سي اتش)
5. رموز ريد سولومون
6. رموز جبرية هندسية
7. رموز ريد مولر
8. رموز مثالية

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

نظرية الترميز تستخدم عدد ن من الابعاد لنموذج المجال . على سبيل المثال، وكم البنسات يمكن أن تكون معبأة في دائرة على سطح الطاولة، أو في 3 أبعاد، كم من الأفكار التي يمكن أن تكون معبأة في العالم . اعتبارات أخرى تدخل في اختيار الرمز . على سبيل المثال، الشكل السداسي يتم تغليفها لتحليل القيد من صندوق مستطيل سوف يترك مساحة فارغة في الزوايا . بما أن الأبعاد أصبحت أكبر، والنسبة المئوية للمساحة الفارغة تنمو أصغر . ولكن في بعض الأبعاد، تستخدم التعبئة كل المساحة وهذه الرموز هي ما تسمى رموز «مثالية». الأكواد المثالية الوحيدة الغير بديهية والمفيدة هي المسافة 3 كود الهامنج مع المعايير التي تتفق مع (2^r – 1, 2^r – 1 – r, 3), و [23,12,7] الثنائي و [11,6,5] أكواد غولي الثلاثية .[2][3]

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

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

المقال الرئيسي: رمز التلافيف

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

لذلك نجد عموما أن خرج نظام التشفير التلافيفي، الذي هو الالتواء لبت المدخلات، ضد دول التشفير الالتواء، سجلات .

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

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

وتستخدم رموز التلافيف في أجهزة المودم (V.32, V.17, V.34) وفي الهواتف النقالة GSM، وكذلك أجهزة الأقمار الصناعية والاتصالات العسكرية .

المقال الرئيسي: التشفير

التشفير أو الترميز التشفيري هو ممارسة ودراسة تقنيات الاتصالات الآمنة في ظل وجود أطراف ثلاثة (وتسمى الخصوم).[6] وبصفة عامة، الأمر يتعلق ببناء وتحليل البروتوكولات التي تمنع الخصوم.[7] الجوانب المختلفة في مجال أمن المعلومات مثل سرية البيانات، سلامة البيانات، التوثيق، عدم التنصل [8] هي محور التشفير الحديث . يوجد التشفير الحديث عند تقاطع تخصصات الرياضيات، علوم الكمبيوتر، والهندسة الكهربائية. وتشمل تطبيقات الترميز بطاقات الصراف الآلي، كلمة السر للكمبيوتر، والتجارة الإلكترونية.

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

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

المقال الرئيسي: رمز الخط

رمز الخط (ويسمى أيضا تحوير النطاق الأساسي الرقمي أو طريقة نقل النطاق الأساسي الرقمي) هو الرمز المختار للاستخدام ضمن نظام الاتصالات لأغراض نقل النطاق الأساسي . وكثيرا ما يستخدم خط الترميز لنقل البيانات الرقمية .

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

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

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

الفئة العامة الأخره من الرموز هي رموز تكرار الطلب الاوتوماتيكي أو التلقائي (ARQ). في هذه الأكواد يضيف المرسل التكرار لكل رسالة لفحص الخطأ، عادة ما تكون عن طريق إضافة اختيار البت .إلو كان اختيار البت لا يتفق مع بقية الرسالة عند وصولها، المستقبل سوف يطلب من المرسل إعادة إرسال الرسالة . الجميع ما عدا أبسط البروتوكولات تعتبر منطقة شبكة واسعة تستخدم (ARQ). وتشمل البروتوكولات المشتركة SDLC (IBM), ميفاق ضبط الإرسال (Internet), بروتوكول X25 (International) وغيرها الكثير. وهناك مجال واسع من البحوث حول هذا الموضوع بسبب مشكلة مطابقة الحزمة المرفوضة ضد الحزمة الجديدة . هل هي واحدة جديدة أو أنها ليست لإعادة الإرسال؟ عادة ما يتم استخدام ترقيم المخططات، كما هو الحال في بروتوكول التحكم بالنقل في شهر سبتمبر لسنة 1981.

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

يتم ترميز المعلومات بشكل مشابة في الشبكات العصبية للدماغ، في معالجة الإشارات التناظرية، والالكترونيات التناظرية. وتشمل جوانب الترميز التناظري analog coding تصحيح الخطأ التناظري analog error correction ، [9] ضغط البيانات التناظرية analog data compression [10] والتشفير التناظري .[11]

الترميز العصبي هو مجال علم الأعصاب المرتبط بالقلق مع كيفية تمثيل المعلومات الحسية وأخرى في الدماغ عن طريق شبكات من الخلايا العصبية. الهدف الرئيسي لدراسة الترميز العصبي هو لتحديد خصائص العلاقة بين التحفيز والردود العصبية الفردية أو المجموعة والعلاقة بين النشاط الكهربائي للخلايا العصبية في المجموعة .[12] ويعتقد أن الخلايا العصبية يمكن تكويد كل من المعلومات الرقمية والتناظرية، [13] وأن الخلايا العصبية تتبع مبادئ نظرية المعلومات وضغط المعلومات، [14] واكتشاف وتصحيح [15] الأخطاء في الإشارات التي يتم إرسالها في جميع أنحاء الدماغ والجهاز العصبي على نطاق أوسع .

• خاصية تصحيح الخطأ
• نظرية المعلومات

• بوابة اتصال عن بعد