مدخل الى علم التشفير

[azizever83 28]

السلام عليكم ورحمة الله وبركاته والصلاة والسلام على أشرف الأنبياء والمرسلين سيدنا محمد وعلى اله وصحبه وسلم

لقد لفت إنتباهي بالصدفة سؤال أحد الإخوة عن Arithmetic coding فأحببت أن أقوم بوضع بعض الدروس بخصوص مثل هذه الانواع من الخوارزميات

مما لاشك فيه أن خوارزميانت التشفير في عملية نقل البيانات وضغطها تلعب دورا مهما في عالم الاتصالات والحاسب الالي فهنالك العديد من خوارزميات ضغط البيانات التي تعتمد عليها العديد من التطبيقات التي نستخدمها في حياتنا اليومية مثل zip files, jpg images, pdf ,,,, الخ,,,

سوف أقوم ان شاء الله بعمل دروس بسيطة عن هذه الخوارزميات "خوارزميات التشفير" . لهذا يجب أن نعرف أنه في علم التشفير coding theory يوجد نوعين من أنواع التشفير هما source coding و channel coding

Source coding أو تشفير المصدر الغرض منه الضغط compression بحيث يتم تخزين أو ارسال البيانات بحجم اصغر من حجمها مع المحافضة على محتويات هذه البيانات وهذا ما يعرف ب lossless compression وايضا بالنسبة لتشفير المصدر يوجد نوع اخر يسمى lossy coding وفي هذه الحالة يكون هنالك فقد في البيانات اثناء عمليات الضغط

النوع الثاني وهو عبارة عن channel coding أو تشفير القناة والغرض منه هو تصحيح الاخطاء التي قد تنجم في عملية نقل البيانات أو تخزينها,,,, والمقصود هنا ب channel هي الوسيلة المستخدمة في نقل البيانات مثل cable أو التخزين مثل CD

وفي البداية أود أن انوه أن كلا العمليتان مرتبطتان ببعضهما البعض بحيث تكون عملية الضغط أو تشفير المصدر هي الاولى ثم عملية تشفير القناة كما هو مبين في الرسم بالاسفل:

سأبدا إن شاء الله باساسيات التشفير بحيث يتسنى للكل فهم المواضيع المتقدمة إن شاء الله

وأستسمحكم عذرا باستخدام بعض المصطلحات باللغة الإنجليزية أو إن كانت الترجمة غير دقيقة

الجزء الاول ويتضمن تشفير المصدر أو الضغط source coding or compression

سأبدا إن شاء الله بطرح موضوع Prefix code

ثم Kraft-Mcmillan inequality theorem

- Huffman coding

- Adaptive Huffman coding

- Arithmetic coding

- Fanno Shannon coding

- Lembel Ziv أو dictionary coding

ثم الجزء الثاني إن شاء الله عن Channel coding ويشمل

-

- Error detecting and correcting

- Matrix generator , Parity check matrix, syndrome decoding coset encoding

- Linear Codes

- Dual Codes

- Deletion/insertion errors.

- Surveying Codes

أتمنى من الله أن يوفقني ألى ما فيه خير لي ولكم

[azizever83 28]

الدرس الثاني

السلام عليكم ورحمة الله وبركاته

لم نبدأ بعد في عمليات التشفير الى حد الان,,, أود أن أنوه إلى أنه يجب عليكم أن يكون لديكم المام ببعض قواعد الاحتمالات التي هي اساس نضرية المعلومات information theory ولكن إن لم يكن لديك فلا مشكلة سأقوم بشرح ذلك ولكن الأمر يعتمد على مدى طلبات الاخوة لأن ذلك سياخذ بعض الوقت ,,,, عموما سأقوم اليوم بعرض بعض الاساسيات الخاصة بنضرية المعلومات information theory واعتذر إذا لم تكن الترجمة دقيقة :

نضرية المعلومات في علم التشفير تتعلق بما مدى كفاءة التشفير وما اذا كان العمل الذي نقوم به سليم أم لا؟ عموما إن ام تكن هذه العبارات غير واضحة فلا داعي للقلق,,, لأنها ستكون أوضح مع تقدمنا وتعمقنا في هذه الدورة.

ما هي قيمة المعلومات التي نحتاجها ؟

نود أن نعرف قبل كل شئ ما هي البيانات المهمة التي نحتاجها في عملية التشفير , وهنا سأقوم بعرض مثال بسيط ولكن مهم حتى نعرف الاساسيات المبني عليها source coding

فعلى سبيل إذا اردنا أن نلعب لعبة وهي أن يختار شخص ما شخص اخر من بين مجموعة من الاشخاص ولا يخبر أي أحد بذلك ويتم سؤال هذا الشخص بعض الاسئلة على أن تكون الإجابة بنعم أو لا Yes or No بحيث نعطي لنعم قيمة 1 ولا 0

السؤال هنا ماهي الاسئلة المهمة؟ اي ما قيمة المعلومات التي نحتاجها عند سؤال مثل هذا السؤال؟ كم من المعلومات نحتاج حتى نستطيع أن نتاكد من أنه فلان؟

هل يوجد أي فائدة من تكرار نفس السؤال؟؟ طبعا لا الا في حالة اننا نتوقع ان الاجابة تتغير وهذا ما يعرف ب Entropy of source أو عدم اليقين وركزوا جيدا فهذا الممصطلح مهم جدا جدا في information theory وباختصار على سبيل المثال عندما نقوم بقذف قطعة نقود في الهواء فإن المرة الأولى لا تعطينا أي معلومة عن المرة القادمة

وقانون الانتروبي هو

سنتطرق لهذا الموضوع أكثر إن شاء الله

لنعد الى اللعبة وقد قمت بعمل رسم توضيحي للعبة ولاحظو أن كل شخص تم تمييزه في الجدول الذي تحت الشجرة بكود يختلف عن التاني,,, فحاليا بدل من ارسال اسم الشخص سنقوم بارسال الكود الخاص به كشفرة ولاحظوا أن الترقيم يبدا من الاسفل الى الاعلى

ناتي الان الى مصطلح اخر مهم جدا فيي عملية التشفير والضغط الخاص بالمصدر source coding هذا المصطلح هو redundancy أو التكرار

إن مصطلح redundancy مهم جدا فهو يعني الضغط فلاحظو في المثال الاسفل

mst ids cn b xprsd n fwr ltrs, bt th xprnc s mst nplsnt

فبدلا من ارسال

Most ideas can be expressed in fewer letters, but 
the experience is most unpleasant.

فلاحظوا أنه تم اختصار الجملة الى حوالي 34 حرف بدلا من حوالي 70 حرف وهذا ما يعرف ب lossless compression أي الضغط مع عدم فقدان المعنى,,,,,, بمعنى اخر أن الجمله لها خاصية Redundancy

إن المثالين السابقين redundancy ومتال الشجرة الخاصة بالتشفير هما مثالان مهمان كمدخل لفهم الية عمل التشفير

وفقني الله واياكم ولنا لقاء باذن الله في الدرس القادم

ملاحظة ,,,, في الجدول المرافق للشجرة فان الترقيم من اليسار الى اليمين وسنرى ذلك إن شاء الله باكثر وضوح في huffman coding

[azizever83 28]

الدرس الثالث Prefix Code

السلام عليكم ورحمة الله وبركاته

اليوم إن شاء الله بسيط ولكن مهم سنتحدث عن درس مهم جدا في عملية encoding and decoding

نحن نعرف جميعا أن عملية encoding تتم عن طريق جهاز الارسال transmitter بينما عملية decoding تتم عن طريق جهاز الاستقبال ,,,, وذلك لان البيانات يجب عدم الاطلاع عليها الا من قبل الاشخاص المخولين بذلك Authorized persons وهذا ما يعرف بـ Confidentiality

لاحظو في الصورة اسفل وجود Eve/noise/Oscar وهذا المصطلح يعرف ايضا بـ adversary ومهمته هي التنصت على الاتصال ومحاولة الاختراق :dry:

المهم ,,,,,

إن عملية التشفير يجب أن تخضع الى بعض المتطلبات التي تجعل عملية decoding ممكنة ,,,,, نعم ممكنة,, فلو لم تكن عملية التشفير بطريقة سليمة efficient فان جهاز الاستقبال لن يستطيع فك التشفير أن انه سيقوم بذلك بشكل خاطئ

هنا ناتي الى مصطلح Prefix code فعلى سبيل المثال لنلقي نضرة على الكود اسفل

C(1)=0, C(2)=010, C(3)=01, C(4)=10

يبدو هذا الكود للوهلة الاولى كود عادي ولكن ركزوا جيدا ماذا لو استقبل جهاز الاستقبال

 c(3)C(1) 

أو

C(1)C(4)

فكيف سيتعامل جهاز الاستقبال مع هذه المشكلة اليست

C(1)C(4)=c(3)C(1)=C(2)؟

إن هذا الكود ليس uniquely decodable بمعنى انه لايمكن فك تشفيره بنتيجة واحدة فقط

هنا تأتي اهمية مصطلح Prefix code وبصراحة لا أستطيع أن أترجم هذا المصطلح المهم يعني أن كل رمز أو كود يتميز عن التاني ولا يوجد أي تداخل بين كودين

فعلى سبيل المثال الكود أسفل

C(1)=0, C(2)=10, C(3)=110, C(4)=111

يعتبر uniquely decodable بمعني لو دققنا في هذا الكود أو أنه تم استقباله على النحو التالي

فلو افترضنا انه تم استقبال الكود على النحو التالي

  01011111010

فهو ببساطة وبدون أي صعوبة عبارة عن

0, 10, 111, 110, 10

ومن تم فتن الكود يعتبر prefix code or uniquely decodable

ولكن سؤال هنا هل الفاصلة مهمة؟؟؟

طبعا لا

حيث أن جهاز الاستقبال عند استقبال اول رمز ولنقل صفر على سبيل المثال فانه سسيقوم بالكشف في lookup table ماهي الحروف او الارقام التي تبدا بـ صفر سيجد أنه C(1) اوكي تم سينضر الى باقي الرموز أي منهم يبدا بصفر فلن يجد ويسقوم بتخزين الرقم الاول على انه C(1) تم نفترض أن الرمز التاني تم استقباله هو 10 فسيقوم بالبحث على جميع الرموز التي تبدا بـ1 سيجد انها تلاتة رموز

 C(2), C(3) & C(4)

اممممم مشكلة؟؟؟؟ :huh: لا سيقوم بالنظر الى الرقم التاني وهو واحد هل هنالك اكتر من رمز يبدا بصفر تم واحد؟ لا انه فقط c(2) تم نفس المقارنة بين

C(3) and C(4) 

التمييز سيكون على اسااس ثالث بت

اتمنى أن يكون الدرس مفيد

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

وفقني الله واياكم الى كل خير

الدرس القادم إن شاء الله عبارة عن التاكد من ان الكود uniquely decodable عن طريق نضرية kraft-mcmillan inequality

[azizever83 28]

الدرس الرابع The Kraft-McMillan inequality

السلام عليكم ورحمة الله وبركاته

سأقوم بوضع درس خفيف لهذا اليوم إن شاءالله وذلك بسبب إنشغالي ببعض الامور التي حالت دون وجود وقت كافي

إن نضرية The Kraft-McMillan inequality من النضريات المهمة التي يجب تحققها في الكود الذي يحمل خاصية Uniquely Decodablilty أو إمكانية فك تشفير الكود بحل واحد فقط بحيث لا يوجد اي تداخل بين حرفين أو رمزين أو codewords

سأقوم في البداية بكتابة النضرية باللغة الانجليزية ومن تم شرحه الى العربية

For any Uniquely Decodable code over an For any Uniquely Decodable code over an

alphabet D, of size s=|D|, the codeword

lengths L1, L2,,,,, Lm must satisfy the inequality

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

لاعليكم بمعنى آخر أن هذه النضرية قد تنطبق على كود ليس من نوع uniquely decodable

فعلى سبيل المثال الكود

C={0,11,100,110}, D={0,1}, l1=1, l2=2, l3=3, l4=4 

هذا الكود ليس من نوع uniquely decodable ولكن يتحقق فيه شرط Kraft ولكن أي كود من نوع uniquely decodable يتحقق فيه هذ الشرط.

فلنقم بتجربة النضرية على الكود الخاص بالدرس السابق

C(1)=0, C(2)=10, C(3)=110, C(4)=111

هنا D= 2 لأن الكود من نوع binary لاحظوا أنه يمكن ان يكون الكود من نوع ternary أو ثلاثي أي من

{0,1,2}

سنرى ذلك إن شاء الله في درس huffman coding

المهم الان طريقة حساب المعادلة هي كالتالي

1/2+1/2^2+1/2^3+1/2^3=1 

وهو ما يطابق الشرط

بإمكانك أخي الكريم تجربة هذا الكود

ليكن D={0,1,2}

وليكن مجموع الحروف هو 6 وطول كل منها على التوالي هو 1,1,2,4,4,5 ملاحظة سيكون الحل النهائي هو 196/243 الرجاء تجربة الحل وإن لم يكن واضحا فساقوم بتوضيحه أكثر

والسلام عليكم ورحمة الله وبركاته

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

أعتقد أن الجانب النضري قد إنتهى أو قارب على الإنتهاء وساحاول ان ابدا في الجانب الأكثر تشويقا إن شاء الله مثل , huffman coding, Arithmetic coding, Lembel Ziv or dictionary coing وغيرها

أرجوا أن يكون هنالك أكتر تفاعل من الاعضاء

وشكرا

[Z3r0n3 125]

هل هنالك طريقة (موقع) لتحميل الصور بشكل دائم ؟

ارفع الصور على المنتدى

في الجدول المرافق للشجرة فان الترقيم من اليسار الى اليمين

تقصد من اليمين إلى اليسار ;)

ملاحظة: أنت انتقلت من الدرس الثاني إلى الدرس الرابع، هل نسيت وضع الدرس الثالث أو هو خطأ في الترقيم؟

هذه محاولتي:

A={0,1,11,0022,0112,21112}
1/3+1/3+1/3^2+1/3^4+1/3^4+1/3^5=2/3+1/9+2/81+1/243=(162+27+6+1)/243=196/243

نحن في انتظار الدرس القادم ^_^

بالتوفيق

[azizever83 28]

ارفع الصور على المنتدى

تقصد من اليمين إلى اليسار ;)

ملاحظة: أنت انتقلت من الدرس الثاني إلى الدرس الرابع، هل نسيت وضع الدرس الثالث أو هو خطأ في الترقيم؟

هذه محاولتي:

A={0,1,11,0022,0112,21112}
1/3+1/3+1/3^2+1/3^4+1/3^4+1/3^5=2/3+1/9+2/81+1/243=(162+27+6+1)/243=196/243

نحن في انتظار الدرس القادم ^_^

بالتوفيق

أخي الكريم إجابة صحيحة شكرا على المشاركة

بالنسبة للدرس الثالث فقد كان هنالك خطافي الترقيم فقط

بالنسبة للكود من اليمين الى اليسار فأنا اقصد ترقم كل شخص من 01 ولاحظ انه من الاسفل الى الى الاعلى

بارك الله بك على هذه الدروس

أولا أين الرس الثالث أخي الكريم

ثانيا صراحة الدرس الأخير كان غامض ولم افهم شيئ من المعادلات والاكواد

يا ريت يتم شرح مثال بالتفصيل

دائما نترقب المزيد

أخي الكريم ,,, شكرا على مرورك وتواصل

لا تقلق سأقوم بشرح الدرس بأكثر تفصيل فقد كتبت الدرس في وقت متاخر الامر الذي لم يسمح لي بوضع العديد من التفاصيل

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

[azizever83 28]

أخي بارك الله فيك.. ما هو مصدرك؟:)

مثل هذه المواضيع تكثر دراستها في علوم "الاتصالات" وعلوم الحاسب .. وبدا لي من أسلوب شرحك أن مصدرك كتاب في "الاتصالات" ؟

وفقط لدي ملاحظة بسيطة، أعتقد أن ما يستصعبه كثير من الأعضاء في شرحك هو وضع معادلات رياضية بشكل مفاجيء دون التمهيد لها، أو الاستدراك بشرحها؟

واصل، دمت على خير.

أخي الكريم ,,,, لقد كانت هذه المادة من المقررات الدراسية,, وهذا هو مصدري أي ما قد درسته في هذه المادة فأنا لست خبيرا في هذا المجال وانما الامر الذي جعلني أكتب في هذا المجال هو انني وجدت صعوبة في الحصول على مصادر عربية في هذا المجال مع انه مجال شيق ومهم ,,, وبصراحة عرفانا مني لما تعلمته من هذا المنتدى فقد قررت أن أحاول كتابة مواضيع عن هذا المجال

النقطة الثانية هي أنني الجا في بعض الاحيان الى الاستعانة ببعض المصادر من الانترنت ولكن ليس هنالك مصدر معين ولكن هنالك كتاب بعنوان Coding Theory: A First Course يعتبر ممتاز في هذا المجال

ايضا بالنسبة للمعادلات الرياضية اوافقك الراي وساقوم بعمل ما في وسعي لكي اشرح هذه المعادلات بطريقة مناسبة ,,, ولكن المشكلة هي في كتابة الرموز لذلك ساقوم بالاستعانة ببرنامج latext فهو يساعد كثيرا على كتابة الرموز الرياضية والمعادلات

[azizever83 28]

السلام عليكم ورحمة الله وبركاته

الأخ vector_ever ,,, الإخوة الاعضاء

سأقوم اليوم بشرح مزيد من الأمثلة عن الدرس السابق حتى تتضح الرؤيا أكثر

أولا دعوني أشرح لكم المعادلة الخاصة بنضرية Kraft-McMillan inequality

إن نضرية Kraft-McMillan تنص على أن مجموع أطوال الحروف في كل كود مضروب في الاس -1 أو المقلوب يجب أن يكون أقل من أو يساوي 1. بمعنى أنه إذا وجدا أي كود أكبر من في هذه المعادلة اكبر من واحد فهذا يعني أن الكود لايمكن أن يكون من نوع uniquely decodable

اما بالنسبة الى المعادلة فإن ll1, l2,,,,,lm يعني طول كل رمز من الرموز التي هي مع بعضها تكون الكود نفسه ,,, بمعنى

c1=1, C2=010, C3=0011

ففي هذا المثال طول c1=1 و طول c2=3 وطول C3=4

أي

l1=1, l2=3, l3=4

أما بالنسبة الى S فهو نوع البيانات المستخدم في عملية التشفير وهنا في هذا المثال من نوع

Binary: {0,1}

أما بالنسبة الى li فهو تسلسل الرمز حسب وجوده في الكود

فخذ على سبيل المثال الكود المبين بالاسفل

من الواضح أن هذا الكود ليس من النوع Uniquely decodable ولكن لنجرب نضرية Kraft

لنعد الى الكود الاول

c1=1, C2=010, C3=0011

ونطبق قانون كرافت

أتمنى أن تكون الفكرة قد وصلت

الآن :) بإمكانكم تجربة هذه الاكواد

A.{0,1,21,10,11,210}, B.{0,00,11,110,012,0110}, C. {0,1,2,0102},  

ملاحظة, واحد من الاكواد اعلاه فقط يحقق شرط Kraft :)

دمتم في امان الله

[azizever83 28]

شكرا اخي على شرحك هذا المثال مجددا

لكن لدي سؤال في شرحك قد ذكرت هذا التفصيل انه

l1=1, l2=3, l3=4

من أين اتت هذه الارقام

لم افهمها

وايضا ما المقصود بالسطر الاخير في شرحك

A.{0,1,21,10,11,210}, B.{0,00,11,110,012,0110}, C. {0,1,2,0102},  

زشكرا

السلام عليكم اخي الكريم vector

بالنسبة الى l1=1 مقصود به أن اول رمز في الكود طوله واحد بت وهو عبارة عن 1

l2= 3 فمعناه أن طول الرمز الثاني هو 2 بت 010

l3=4 فمعناه أن طول الرمز الثالث هو 4 بت 0011

بالنسبة للكود

A.{0,1,21,10,11,210}, B.{0,00,11,110,012,0110}, C. {0,1,2,0102},  

فأنا أود منك أنت والاخوة الاعضاء تجربة نضرية kraft بحيث يتم ايجاد اي من الكودات يحقق الشرط

وشكرا

[azizever83 28]

الدرس الخامس Huffman coding

السلام عليكم ورحمة الله وبركاته,,,,,

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

إن الهدف الاساسي من عملية تشفير المصدر source coding هو الضغط compression كما هو الحال في zip files على سبيل المثال,,,

نحن نعلم أن ascii code يقوم بتشفير الحروف من ألف الى الياء ومن صفر الى تسعة بنفس الطول اي 8 بت وهو ما يسمى block coding or fixed length coding بغض النظر عن أن بعض الحروف قد تكون اكتر استعمالا من الاخرى

فعلى سبيل المثال فإن الحروف المتحركة a,e,I,o هي اكثر إستعمالا من بعض الحروف الأخرى مثل z,q,x. لذلك فإنه من المهم وجود وسيلة أكثر عمليا من هذه في بعض العمليات. إن الميزة الاساسية أو السمة في هذا النوع من التشفير ASCII هو السرعة عند تنفيذ البرامج,, ولكن في عمليات التخزين وإرسال البيانات فإن ASCII code ستأخذ عملية التخزين أكبر حيز من الذاكرة كما أن عملية الاسال ستكون أقل سرعة.

هنا ناتي ألى أحد انواع الضغط المستخدمة في عملييات تخزين ونقل البيانات. نبدأ اولا بخوارزمية Huffman . على العكس من ASCII coding فان Huffman coding تقوم بضغط بحيث يتم تمثيل الحروف الاكتر استعمالا في الملف ولنقل هنا النص المراد ارساله باقل عدد من bits وعادة ما يكون واحد بت فقط كما سنرى لاحقا. لاحظوا أنه بالانتقال من ASCII code الى Huffman code فإنه تم تقليل حجم الحرف من 8 بت الى 1 بت فقط الامر الذي سيزيد من كفاءة البرنامج في عمليات الارسال والتخزين على حد السواء. مع ملاحظة أن هذا الملف لن يفقد أي شي منه وهذا ما يعرف ب lossless copressionوقد تم الحديث عن هذا النوع من التشفير في الدرس الأول.

خوارزميةHuffman coding تعتبر بسيطة وسهلة وليس بها أي تعقيد.

إن أهم استخدامات Huffman coding هو ملفات ضغط الصور مثل JPG, JPEG , PNG , MPEG,

أيضا تطبيقات ضغط الملفات GZIP, WINZIP,

بالنسبة لملفات الصوت لدينا على سبيل المثال MP3, ACC format يتم فيها إستخدام Huffman coding

المهم نأتي الان الى الجانب الاهم وهو طريقة عمل Huffman coding

كما ذكرت لكم في البداية فان الحرف او الرقم الاكثر تكرارا في الملف سيتم تعيين اقل عدد من bits له.

ملاحظة: إن العملية تعتمد على الاحتمالات بحيث عندما أقول الحرف الاكثر تكرارا فأنا أعني أنه الحرف الذي يحتوبي على نسبة اعلى من الاحتمالات

فعلى سبيل المثال لو أخذنا هذا النص

aaaaebbade

فإن الحرف a الاكثر تكرارا ثم b,e ثم d وسنرى أن a سيكون له اقل طول ثم b, e ثم d

المهم إن الخطوات التي تتبع في خوارزمية Huffman لبناء Huffman tree هي كالتالي

1- ترتيب الحروف ترتيبا تصاعديا بناء على نسبة الاحتمالات

2- نقوم بتوصيل اقل حرفين ونقوم بوضع المجموع في النود الذي يلتقي فيه هذين الحرفين

3- نقوم بالكشف عن باقي الاحتمالات هل هنالك اي منهم اقل من مجموع هذين الحرفين الذين تم جمعهما في الخطوة التانية؟ اذا كانت الاجابة نعم نقوم بنفس الخطوة السابقة مع الحرفين الاقل احتمال

4- نقوم بتكرار نفس العمل حتى نصل الى 1 وهو مجموع جميع الاحتمالات

لنبدا على بركة الله باول مثال عملي وبسيط

لنفترض أنه لدينا مجموعة من الرموز وهي كالتالي

{a,b,c,d}

مع الاحتمالات التالية على التوالي

{ 0.5, 0.3, 0.15, 0.05}

بمعنى ان

 a=0.5, b=0.3, c= 0.15, d=0.05

باستخدام الخطوات المبينة أعلاه

1- هنا لاحظو أن كلا من c, d هما الاقل احتمال نقوم بجمعهما معا الناتج = 0.2

2- الان أقل احتمالين لدينا هما مجموع c,d =0.2 و b=0.3 نقوم بجمعهما معا لنحصل على 0.5

3- الآن لم يبقى لدينا الا الرمز a نقوم بجمعه مع مجموع الخطوة 2 لنحصل على 1 صحيح

الآن سأقوم بتوضيح ذلك باستخدام الشجرة

الان بعد ذلك نقوم بتخصيص الكود لكل حرف وطول الكود بالبت

لاحظو في الجدول التالي كافة التفاصيل أن أطول حرف أخذ فقط 3 bits وأقصر حرف أخذ فقط 1 bits بدلا من 8 bits في حال استخدام ASCII code وهو ما يعرف بـ compression

الان نقوم بحساب معدل كم بت سياخد كل حرف

الطريقة بسيطة وهي أن نقوم بضرب كل حرف مع طوله Li ونجمعه بالحرف الذي يليه كالتالي

1*0.5+2*0.3+ 3*0.15+3*0.05= 1.7 bits 

فقط كل حرف سياخذ 1.7 بت بدلا من 8 بت

جميل اليس كذلك ؟؟؟

اتمنى أن تكونوا قد استفدمتم من الدرس

لنا لقاء إن شاء الله في الدرس القادم

Adaptive huffman coding

دمتم في رعاية الله

[azizever83 28]

أخي الكريم

شكرا على تواصلك

السلام عليكم،

هذه محاولتي:

B={0,00,11,110,012,0110}
1/3^1+2/3^2+2/3^3+1/3^4=1/3+2/9+2/27+1/81=(27+9+3+1)/81=40/81<=1

نعم الاجابة B هي الصحيحة

ماهو غرض استعمال نظرية Kraft-McMillan inequality ؟

بالنسبة لدرس الـ Huffman Coding

بصراحة خوارزمية بناء الـ Huffman Tree ليست واضحة، فمثلا كيف نقوم بحساب الاحتمالات؟ كيف نرسم الشجرة؟ كيف يكون الضغط؟ كيف يكون فك الضغط؟ و الكثير من الأسئلة... الدرس مهم و يحتاج الكثير من الشرح.

1*0.5+2*0.3+ 3*0.15+3*0.05= 1.7 bits 

أخي، البت (Bit) هو أقل وحدة تخزين في ذاكرة الحاسب، يأخذ القيمة 0 أو 1 وهو غير قابل للتجزئة. يعني لا يوجد 1.7 Bits، أظنك تتحدث عن و حدة تخزين أخرى

أخي الكريم في المثال السابق كانت الاحتمالات موجودة مسبقا ولكن ساقوم بوضع درس عن كيفية حساب الاحتمالات في حال أن الاحتمالات غير موجودة ,,,,

سأقوم بشرح الدرس باكثر تعمق بحيث تكون الرؤيا واضحة إن شاء الله الله ولو اضطرني ذلك إلي أن أقوم برسم الشجرة باليد :)

بالنسبة لموضوع البت كلامك صحيح وسؤال ممتاز بارك الله فيك لقد غابت عني هذه النقطة بالنسبة 1.7 هو عبارة عن المعدل العام يعني أن في عمليه الضغط او التشفير هذه فان معدل طل كل حرف هو عبارة عن 1.7 بت ولاحظ أن جميع الحروف بعد اجراء عملية التشفير قد أخذت 1و 2 و 3 بت وقمنا بضرب هذه الاطوال في الاحتمال الخاص بكل حرف

ولكن أعتقد ولست متاكد من أنه يمكن أن يكون هنالك كسور في البت وهو سؤال مهم وساحاول ان ابحث في الموضوع باذن الله

من الجيد أن تضع تمارين لنتمكن من معرفة مدى استيعابنا للدرس و تثبيت المعلومات.

جزاك الله كل خير على الدروس

بالتوفيق

[azizever83 28]

مرحبا,,,,,,,

إن هذا الدرس لكي أوضح للاخوة الاعضاء والأخ Z3r0n3 على سبيل الخصوص كيفية حساب الاحتمالات وكيفية رسم الشجرة خطوة بخطوة وكذلك عملية فك الضغط

على بركة الله

في المثال السابق كان لدينا الاحتمالات موجودة مما يجعل الامر اسهل .... ولكن في حالة لا يجود لدينا الاحتمالات ما هو الحل؟؟

الحل هو ما يعرف بـ two pass Huffman coding بمعنى أن نقوم بالعمل مع الكود مرتين المرة الاولى حساب الاحتمالات تم البدء في عملية التشفير,,,, امممممم الامر يبدو مبهم بعض الشئ صح؟؟

لا عليكم لناخذ على سبيل المثال النص التالي

debbcadced

نقوم أول شئ بحساب تكرار كل حرف مع الاخذ بعين الاعتبار مجموع الحروف هنا وقد إخترت أن يكون المجوع عشرة حتى تكون الرؤيا أسهل

فيكون لدينا

الرمز a b c d e

التكرار 1 2 2 3 2

بمعنى أخر

, b= 0.2, c=0.2, d=0.3, e=0.2 a=0.1

الان حتى تتضح الرؤيا في عميلة بنا الشجرة نلاحظ أن اصغر رقمين عندنا هما 0.1 و 0.2 مع ملاحظة أن 0.2 مشتركة بين b, c, e هنا اي من الحروف اخترنا لا يهم ولكن ساختار الحرف b اولا حتى نحافظ على الترتيب

0.1+0.2=0.3 ولنقل ان هذا الرمز عبارة عن ab أي بمعنى أنه تلاقيهما في الشجرة وهذه النقط تعرف بـ node

الان لدينا ab{0.3} , c{0.2}, e{0.2}, d{0.3} 

لاحظوا الان ان كلا c, e هما الاصغر فنقوم بجمعهما معا ولنقل ce ويكون المجموع 0.4

الان لدينا الناتج كالتالي

ab{0.3} , ce{0.4}, d{0.3} 

الان لدينا 0.3 و 0.3 مجوعهما هو 0.6 تم نجمع الرقم مع اخر رقم لدينا وهو 0.4 ليكون الناتج 1 وهو ناتج الاحتمالات

ملاحظة يسمى النقطة 1 root

الآن لنقم برسم الشجرة على بركة الله

لاحظوا أن الشكل ليس كالدرس السابق ولكن نفس الطريقة فقط قمت بتدوير الشجرة حتى اشرح لكم طريقة فك الضغط

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

لاحظوا أنه الواحد في اتجاه اليمين والصفر في اتجاه اليسار وسيفيدنا هذا التنسيق في عملية فك الضغط

الان ساشرح لكم عملية فك الضغط

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

فعلى سبيل المثال لو أردنا أن نفك تشفير الكود التالي

001100111001

فإن الاجراء سيكون كالتالي

بما أن أول حرف هو 0 فإننا نتجه نحو اليسار الرقم الثاني هو صفر كذلك فنتجه ايضا نحو اليسار من النود node تمام؟؟ هنا تنتهي الشجرة يعني ان أول حرف هو حرف b

ثم بعد ذلك أول حرف يصادفنا هو الواحد يعني أننا يجب أن نتجه نحو اليمين هذه المرة ثم أيضا الرقم الثاني هو واحد فاننا نتجه يمين ونجد أن الشجرة إنتهت وتوقفنا عند الحرف e يعني أن الحرف الثاني هو b

نستمر على نفس المنوال بحيث يكون الناتج النهائي لعملية فك التشفير هو bebe!

إنتهى الدرس أتمنى أن تكونوا قد استفدتم أكثر

lمعذرة على الرسوم فأنا أستخدم برنامج محرر النصوص الوورد والرسام :)

في رعاية الله

[azizever83 28]

سؤال

الرجاء المحاولة

تطبيق huffman على

 a= 0:35; b = 0:25;  c = 0:20; d = 0:12;  e = 0:08 

بالتوفيق ان شاء الله

تم تعديل 27 Jun 2012 بواسطه azizever83

[azizever83 28]

الاخوة الاعضاء

السلام عليكم ورحمة الله وبركاته،،،،،،،

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

السؤال هو

هل بالامكان جمع رقمين بحيث نحصل على الناتج صفر مع العلم ان هذين الرقمين ليسا معكوس جمعي؟ اي على سبيل المثال 15+8 =0

هل بالامكان ان نجد عددين حاصل ضربهما يساوي صفر مع العلم ان ليس اي منهما يساوي صفر علىسبيل المثال 9*8=0

اعتقد ان الاجابة ليست صعبة لطلبة علوم الحاسب وطلبة الاتصالات

شكرا

[azizever83 28]

السلام عليكم،

اسمح لي أخي بهذه الإضافة:

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

احتمال حرف=(عدد تكرار الحرف×طول النص)÷100
إضافة ممتازة شكرا لك ننتظر منكم المزيد من المناقشات والاضافات 

هذه محاولتي:

a= 0.35; b = 0.25;  c = 0.20; d = 0.12;  e = 0.08

ed{0.2} a{0.35} b{0.25} c{0.2}
edc{0.4} ab{0.6}
edcab
========
; some ASCII art ;)

                 ROOT
                  |
            -------------
           |             |
         0 |             | 1
       ---------         |
      |         |        |
    0 |         | 1      |
   -------      |      -----
  |       |     |     |     |
0 |       | 1   |   0 |     | 1
  e	  d     c     a     b

تمام ولكن أين باقي العمل :) مثل الكود وطول الكود Entropy of source

منطقيا لا يوجد.

أخي الكريم يوجد هذا النوع من العمليات الحسابية وهي وهي من أساسيات علم التشفير Encryption وهذا ايضا هو اساس الصعوبة في بعض خوارزميات التشفير مثل خوارزمية RSA, Deffie-Hellman, وكذلك التوقيع الالكتروني digital signature أتمنى ان أجد الوقت الكافي لشرح هذه الخوارزميات بالتفصيل في دروس خاصة ولكن بالتاكيد سأقوم بشرح العمليات الحسابية التي سالت عنها لانها مهمة في مرحلة channel coding

مجددا لا تبحث عن الموضوع في google :wink: ساقوم بشرحه مع ملاحظة أنني لم أجد أي شرح مفصل في المواقع العربية

معذرة على تاخري في الدروس ساحاول أن أضع درس adaptive huffman coding هذه الليلة أو غدا في الليل إن شاء الله

جزاك الله كل خير على المجهود

بالتوفيق

تم تعديل 1 Jul 2012 بواسطه azizever83

[azizever83 28]

الدرس السادس Adaptive huffamn code

في الدرس الفائت تعرفنا على طريقة عمل Huffman code فهذه الخوارزمية تعتبر جيدة نوعا ما,,, ولكن من عيوبها أنه يجب بناء شجرة الترميز Huffman tree قبل عملية التشفير, الضغط أو حتى فك الضغط وهذا يعتبر واحد من عيوب هذه الطريقة

لحل هذه المشكلة تم استحداث طريقة جديدة مبنية على اساس Huffman Code وسميت adaptive Huffman code والفكرة الاساسية في هذه الطريقة او الخوارزمية وجود تزامن بين كلا المرسل والمستقبل synchronizing

يجب ملاحظة أن هذا الدرس يحتاج إلى التركيز مع كل خطوة لأن يجب حساب وزن كل node بحيث لا يكون أحد من nodes بوزن أكبر في مكان أبعد عن root والتبديل من اليمين الى اليسار

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

الإخوة الكرام ,,,, أتمنى أن يأخذ كل واحد منكم ورقة وقلم منذ هذ الدرس ومتابعة الدرس خطوة بخطوة

طريقة عمل الخوارزمية

في البداية فإن عملية الترميز تبدا بـ Node =0 بمعنى أن لم يتم التعامل مع اي حرف بعد

بعد ذلك فإن الحرف الذي سيتم معالجته processing سيكون له وزن weight = weight+1 بمعنى انه في البداية سيكون 1 طبعا سيكون ذلك في الخطوة الثانية.

يتم تحديث الشجرة بناء على اعلى قيمة بحيث أن الحرف الذي به أعلى قيمه سيكون الاقرب الى الروت Root dynamic

في أي وقت من الاوقات يجب ان يكون كلا encoding and decoding tree في نفس الوضع

إن adaptive Huffman code مبنية على افتراض أن جميع الحروف متساوية من حيث الإحتمالات

فلنأخذ على سبيل المثال المثال التالي

acceded

فإن عملية الترميز ستكون على النحو التالي

أولا سنبدا كما أشرت بصفر بإعتبار أنه لم تتم المعالجة لأي من الحروف بعد

ثم بعد ذلك فإن أول حرف هو a وسيكون transmission1 أو t1 ولاحظوا أن الوزن weight أصبح واحد وهو عبارة عن مجموع الحروف التي تم التعامل معها الى حد الان

لاحظوا أن الحرف الذي يتم التعامل معه يكون مضلل بالازرق حتى تكون العملية أوضح

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

ملاحظة في هذه الخطوة فإن c يتم اعطاؤه مصطلح NYT أو Not Yet Transmitted أو esc

الآن

الخطوة المهمة في العملية وهي أن c قد تم التعامل معه من قبل ولديه وزن = 1 وa أيضا لديه نفس الوزن ولكن في هذه الحالة سيكون c لديه وزن اكبر فإن وضع الشجرة سيتغير بيحث أن c سياخذ مكان a والعكس ,,, مع ملاحظة أن الترقيم يزداد في node و root

الآن لدينا ضيف جديد إنه حرف e فسيعامل على نفس معاملة a and c بحيث يكون في أسفل الشجرة إلى حين حضور ضيف آخر ليحل محله أو ياتي نفس الحرف ليقوم برفعهه الى الأعلى :)

الخطوة التالية هي أن مجموع أوزان الحروف ماعدا c يساوي ثلاثة بينما مجموع الحرف c يساوي 2 وحيث أن 3 أقل من 2 فإنه كما ذكرت مسبقا يتم تحديث الشجرة من اليمين الى اليسار بحيث يصبح شكلها النهائي بعد التعامل مع d كما هو مبين بالأسفل ولاحظو أن العمليمة من اليمين الى اليسار يتم بواسطتها المحافظة على أن مجموع nodes متناسق وهذه هي عملية التحديث dynamic

ثم بعد ذلك ماذا لدينا؟؟؟؟

اممممم إنه الحرف e وسياخذ محل الحرف a وسيتم تعديل الشجرة كما في الصورة من اليسار الى اليمين

الآن ,,,,,,

هل هنالك ضيف جديد؟؟؟؟ :cool:

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

ولاحظوا عملية التحديث كما في الصورة من اليسار الى اليمين بحيث يكون الشكل النهائي للشجرة كما هو مبين في أقصي اليمين

أتمنى لكم الاستفادة

الدرس القادم إن شاء الله سيكون بسيط جدا ولكن مهم وهو طريقة تحويل الارقام من ارقام كسرية الى ثنائية

مثلا 0.2, 0.7, 0.95 الخ لأنه سيكون مهم في درس Shannon–Fano coding

أتمنى من الاعضاء الذين ليس لديهم فكرة على الموضوع التواجد في المقاعد الامامية :)

[azizever83 28]

رياضيا غير ممكن ولا واقعيا لذلك نحن نتظر إجابتك

أخ Linuxman

شكرا على المرور

ساقوم بطرح هذا الدرس في الحلقات القادمة إن شاء الله

وبصراحة هذا الدرس سيكون مفيد جدا وفي نفس الوقت سهل وبصراحة لم أجد دروس بالعربي لهذا النوع من الرياضايات مع العلم أنه مهم جدا وهو ما بني عليه صعوبة الخوارزميات الشهيرة مثل RSA, Deffie-Hellman

وغيرها

ولكن ستفاجؤن لانني متاكد بانكم تعاملتم مع هذا النوع من الرياضيات باعتبار أنكم متخصصون في مجال الحاسب الآلي

أتمنى أن أجد الوقت لشرح المزيد من الخوارزميات الخاصة بالتشفير مثل RSA, Deffie-Hellman Al-Jamal Encryption, DES and AES التي قل ما نجد شروحات وافية لها باللغة العربية

بالتوفيق إن شاء الله

[azizever83 28]

السلام عليكم

بالامكان تجربة الدرس السابق من خلال هذاالرابط

[azizever83 28]

الدرس السابع تحويل الاعداد الكسرة الى اعداد ثنائية

بسم الله الرحمن الرحيم

نضرا لأنه في عمليات الضغط والاحتمالات يتم التعامل مع ارقام ذات قيم بسيطة اقل من الواحد الصحيح فإنه في علم الحاسب يجب تحويل هذه الارقام الى اعداد ثنائة أو ما يعرف بـ binary

درس بسيط ان شاء الله ولا اعلم ما اذا كان مهم أم لا باعتبار انه من الممكن ان يكون لديكم دراية بالموضوع,,, ولكن أحببت أن أضعه حتى تكون سلسة الدروس متكاملة إن شاء الله نضرا لأهمية الموضوع في الدرسين القادمين Shannon-fanno و arithmetic code

العملية سهلة جدا وتعتمد على ضرب العدد في 2

فاذا كان الناتج اقل من 1 اي بمعني 0.1215 فاننا نكتب صفر ونعيد عملية الضرب

أما إذا كان الناتج 1.0211 على سبيل المثال فنكتب 1 مع حذف الواحد من النتيجة بحيث يصبح الرقم 0.0211

متى نتوقف اذا؟؟؟؟؟

نتوقف عند الوصول الى الرقم 1 صحيح ولكن في بعض الحالات ندخل في loop فاننا نمثل الرقم بحوالى اربعة bits وهي المراد بها عملية الضغط أي تمثيل الرقم باقل من 8 بت

فلنبدأ

ساقوم بتمثيل الرقم العشري

 (number)10

بينما الرقم الثنائي بـ

(number)2

اسهل مثال هو 0.5

0.5*2= 1

يعني 0.1 بت

0.25*2= 0.5 

اقل من 1 يعني 0.0

نضرب الناتج في 2

0.5*2=1

هنا نتوقف لانه لدينا 1 صحيح

اذن

(0.25)10= (0.01)2

مثال اخر

0.75

0.75*2=1.5

نضع واحد بعد البوينت ونحذفه من ناتج الضرب

0.1

0.5*1=1 نتوقف هنا ونضع الواحد في الناتج

اذن (0.75)10=(0.11)2

الان ناتي الى المثال الذي قلت لكم انه عباره عن loop

0.4
0.4*2=0.8
0.0
0.8*2=1.6
0.01  
0.6*2=1.2
0.011
0.2*2=0.4
0.0110

وها قد عدنا من جديد الى نفس النقطة وهي 0.4

فنقوم بتمثيل العدد (0.4)10 بـ (0.0110)2

أتمنى لكم الاستفادة ,,,, دمتم في حفظ الله ورعايته

[Z3r0n3 125]

السلام عليكم،

بالنسبة لدرس Adaptive Huffman Coding

أنا قمت بتطبيق الخوارزمية على النص "rolor":

"rolor"

t=0
(0)

---| 'r'     ---| 'o'     ---| 'l'     ---| 'o'     ---| 'r'
t=1          t=2          t=3          t=4          t=5
 (1)           (2)         (3)          (4)          (5)
 / \           / \         / \          / \          / \
(0)(1)        (1)(1)      (1)(2)       (2)(2)       (2)(3)
nyt r         / \ r        r / \        o / \        o / \
             nyt o         (1)(1)       (1)(1)       (1)(2)
                           / \ o        / \ r        / \ r
                          (0)(1)       (0)(1)       (0)(1)
                          nyt l        nyt l        nyt l

هل هذا صحيح؟

=====

1+ azizever83

تم تعديل 22 Jul 2012 بواسطه Z3r0n3

[Shadi Habbal 961]

السلام عليكم،

- تم تصحيح أرقام الدروس لذا يرجى المتابعة بالدرس "الثامن" ابتداء من الدرس القادم.

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

- للتنويه، فالمنتدى يمكنك من إدراج وسوم LaTeX، استخدم الوسوم التالية:

[latex][/latex]
أو
[latx][/latx]
أو
[tex][/tex]

الثالث يسمح لك بإدراج نصوص LaTeX داخل السطر ذاته دون الحاجة لوضعه في سطر جديد.

الثاني يسمح لك بإدراجها في أسطر مستقلة بدون إطار بارز

أما الأول فقبيح نسبياً :P

تحياتي.

[Z3r0n3 125]

لاحظت أنه لا يوجد أي تعليق من قبل الأعضاء على درس Adaptive Huffman Coding و أعتقد أنّ سبب ذلك هو أنّ الخوارزمية لم يتم شرحها بشيء من التفصيل. لذلك بعد إذن صاحب الموضوع سأقوم بشرح الخوارزمية من جديد. الموضوع مهم و لا أريده أن يتوقف عند هذا الحد.

=====

أولا نبدأ ببعض الأساسيات:

---[1] تسمى عقدة ( Node) و تميّز بوزنها w و هو مجموع الرموز التي تحملها.

---[2] العقدة باللون الأحمر تسمى Root Node و هي العقدة التي تكون في القمة، العقدة باللون الأزرق تسمى Leaf Node. العقدة بالون الأخضر تسمى Parent Node أما العقدة بالون البنفسجي تسمى "عقدة لم تنقل بعد" (Not Yet Transmitted Node) و يرمز لها بـ NYT.

---[3] عقدتان (w1 و w2) ناتجتان من نفس العقدة (w) يكوّنان بلوك (Block)

خوارزمية "Adaptive Huffman Coding"

عملية نقل رمز تمر بالمراحل التالية:

المرحلة 1:

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

المرحلة 2:

إذا كانت العقدة الحالية هي Root نتوجه إلى المرحلة 3

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

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

المرحلة 3:

نزوّد وزن العقدة و نكمل إلى المرحلة التالية

المرحلة 4:

إذا كانت آخر عقدة تم تزويد وزنها ليست Root Node نتوجه إلى العقدة المالكة لها ثم نقفز إلى المرحلة 2. ماعدا ذلك نتوقف.

تمارين:

قم بتطبيق خوارزمية Adaptive Huffman Coding على النص "aabcecebd"

تم تعديل 23 Jul 2012 بواسطه Z3r0n3

[azizever83 28]

الدرس الثامن arithmetic coding

السلام عليكم ورحمة الله وبركاته وكل عام وانتم بخير,,, هذه هي المشكاركة رقم مائة في المنتدى :)

بسم الله الرحمن الرحيم,,,,

لقد تعرفنا في الدروس السابقة على خوارزمية Huffman والتي تعتبر جيدة في الضغط والتشفير,,, ولكن لا يزال هنالك ما هو أفضل منها فعلى سبيل المثال خوارزمية arithmetic coding والتي تعتبر أفضل من Huffman وما يميز هذه الخوارزمية هو أنها تقوم بضغط النص كاملا الى كود واحد على العكس من Huffman التي تقوم بضغط كل حرف او رمز في السلسلة على حدى ,,, وهنا يمكن أن تتصوروا ما مدى الكفاءة التي توفرها هذه الخوارزمية في الضغط,,,

بمعنى اخر أن Huffman code يعتبر من نوع block coding أي يتم التعامل مع كل حرف على حدى بينما في arithmetic code فانه من نوع stream coding اي يتم التعامل مع كامل النص أو الرساله على . هنالك فرق أخر هو ان arithmetic coding يسمح بتمثيل البت بشكل كسور

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

إن هذه الخوارزمية تعتير جديدة نسبيا مقارنة ببعض الخوارزميات الاخرى

ونضرا للكفاءة التي يوفرها هذه الخوارزمية فانها تستخدم في العديد من مجالات الاتصالات مثل 3g and 4g وفي معالجة الصور فان استخدام خوارزمية arithmetic code في كل من jpeg, jpg, وايضا في تطبيقات المحادثة فعلى سبيل المثال skype تستخدم هذه الخوارزمية وايضا في مجال الرسوميات لدينا macro media flash and adobe flash وفي مجال ضغط الملفات لدينا تطبيقات تستخدم arithemetic code مثل paq and ppm وهذان التطبيقات يوفران كفاءة على الضغط اكبر من winzip and winrar وخصوصا paq فهو يقدم ضغط بكفاءة عالية ولكن العيب الوحيد انه يستغرق وقت اكبر في عمليات الضغط وهذا بصفة عامة احد عيوب هذه الخوارزمية. وايضا في مجال تحرير النصوص لدينا برنامج او تطبيق يسمى DjVU وهو عبارة عن برنامج شبيه ببرنامج pdf ولكن يوفر حجم اكبر ويستخدم عادة في كتابة الكتب الالكترونية.

الآن ناتي الى الجزء الاهم وهو كيفية عمل هذه الخوارزمية,,

إن هذه الخوارزمية كغيرها من خوارزميات الضغط تعتمد على الاحتمالات ولكن طريقة الحساب تختلف عن سابقتها Huffman code. فكما ذكرت لكم فان طريقة الضغط تتم بضغط الرسالة الى كود واحد فقط. وهذه الرسالة مكونة من مجموعة حروف وأو ارقام بحيث يتم تمثيلها بفترة interval من الصفر الى الواحد [0,1) أي بمعنى فترة مغلقة من الصفر ومفتوحة من الواحد )نصف مفتوحة(. وهذه الفترة يتم تقسيمها الى فترات جزئية تكون مغلقة من اليساراي الرقم الاصغر الى الى مفتوحة من اليمين اي الرقم الاكبر. أتمنى ان تكون لديكم فكرة عن موضوع الفترات :( وكلما زاد طول الرسالة أو النص فان تقسيم الفترة الرئيسية من الصفر الى الواحد يزداد مع ملاحضة أن طول الفترة سيكون أقل.

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

قبل أن تكو الامور أكثر تعقيدا أعتقد انه يجب وضع مثال على كيفية حساب الفترات intervals فلو افترضنا على سبيل المثال انه لدينا رسالة مكونة من اربعة حروف

A={a0, a1, a2, a3} والاحتمالات الخاصة بكل حرف هي كالتالي على التوالي من a1 الى a4

pi = {0.5, 0.3, 0.15, 0.05} 

فان

I0=[0,0.5), I1=[0.5, 0.8), I2=[0.8, 0.95),I3=[0.95,1)

حيث أن I0 تمثل الفترة الخاصة بـa0 وهكذا....

الآن ناتي الى مثال بسيط حتى تتضح الرؤيا أكثر عن كيفية عمل الخوارزمية

لنفترض أنه لدينا السلسلة النصية {a,b,c} والاحتمالات هي a=0.5, b=0.25, c=0.25

سيكون توزيع الفترات كما هو مبين بالجدول التالي

لنفترض أنه نريد ارسال الرسالة baca فهذا يعني أن مجال التشفير أو الضغط سيكون في مجال الحرف b لانه اول حرف في السلسلة,, بمعنى أن الناتج النهائي سيكون بين 0.5-0.75

Range = high- low

لنبدا بالعملية أول شي حساب مدى أو طول السلسلة وللرسالة كاملة سيكون 0-1 هذا طبعا قبل العملية low =0, high = 1 .

الخطوة التالية هي أن نحسب range للرسالة وبما أنها تبدا عند الحرف b فان low= 0.5 and high=0.75 عليه فان range =0.75-0.5 = 0.25

يجب ملاحظة أن range يتغير مع كل حرف يتم التعامل معه بحيث يكون اقل كلما زاد عدد الحروف.

الحرف الثاني هو a وهذا الحرف له احتمال يساوي 0.5 يعني نضرب هذه القيمة بقيمة احتمال b ونقوم بجمع الناتج مع 0.5 وهو بداية الفترة الخاصة بالحرف b الذي هو أول حرف في السلسلة عليه فان :

ba= a*b+ low b

= 0.5 * 0.25 + 0.5 = 0.625

بمعنى أن النطاق يبدا من 0.5 وينتهي عند 0.625 أي أن طول الفترة أو range يساوي 0.25

Low=0.5 and high =0.625

الآن الحرف الذي يليه هو c قيمة الاحتمال بالنسبة لــc= 0.25 ولدينا السلسة الان على شكل bac يعني ببساطة نقوم بضرب احتمالات كل من b*a*c ومن تم نقوم بجمعه الى قيمة low range للخطوة السابقة والتي كانت 0.5

bac= 0.25*0.5*0.25+0.5 = 0.03125+0.5 = 0.53125

range = 0.53125

low= 0.53125 and high = 0.625

الان الى الحرف الاخير والذي هو a سنقوم بنفس العملية مع تكرار الضرف في احتمال الحرف a

baca= 0.25*0.5*0.25*0.5 + 0.53125 = 0.546875

عليه فان low= 0.53125 and high= 0.546875

Range= 0.015625

عليه فان الرسالة التي سيتم اسالها هي baca=0.53125

وبالطبع نقوم بتحويل القيمة الى رقم ثنائي كما هو في الدرس السابق

أتمنى أن تكون الرؤيا واضحة وإن لم تتضح ساقوم بشرح امثلة أخرى

[Z3r0n3 125]

عليه فان الرسالة التي سيتم اسالها هي baca=0.53125

كيف لمستقبل هذه الرسالة أن يقوم بفك الضغط؟

[azizever83 28]

كيف لمستقبل هذه الرسالة أن يقوم بفك الضغط؟

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