ما هو روتين الضغط الجيد لهذا السيناريو

Question

أحتاج إلى روتين فك ضغط سريع محسّن لبيئة الموارد المقيدة مثل الأنظمة المدمجة على البيانات الثنائية (البيانات السداسية) التي تتميز بالخصائص التالية:

1. البيانات موجهة 8 بت (بايت) (يبلغ عرض ناقل البيانات 8 بت).
2. لا تتراوح قيم البايت بشكل موحد من 0 إلى 0xFF، ولكن لها توزيع بواسون (منحنى الجرس) في كل مجموعة بيانات.
3. يتم إصلاح مجموعة البيانات بشكل متقدم (لحرقها في Flash) ونادرًا ما يكون حجم كل مجموعة أكبر من 1 - 2 ميجابايت

يمكن أن يستغرق الضغط نفس القدر من الوقت المطلوب، ولكن فك ضغط البايت يجب أن يستغرق 23uS في أسوأ السيناريوهات مع الحد الأدنى من مساحة الذاكرة حيث سيتم ذلك في بيئة موارد مقيدة مثل النظام المضمن (3 ميجا هرتز - 12 ميجا هرتز، وذاكرة الوصول العشوائي 2 كيلو بايت) .

ما هو الروتين الجيد لتخفيف الضغط؟

يبدو التشفير الأساسي لطول التشغيل مسرفًا للغاية - أستطيع أن أرى على الفور أن إضافة مجموعة رأس إلى البيانات المضغوطة لاستخدام قيم البايت غير المستخدمة لتمثيل الأنماط المتكررة كثيرًا من شأنه أن يعطي أداءً استثنائيًا!

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

أرغب في الحصول على بعض الأمثلة "الجاهزة للاستخدام" لتجربتها على جهاز كمبيوتر حتى أتمكن من مقارنة الأداء مقابل RLE الأساسي.

Answer 1

الحلان اللذان أستخدمهما عندما يكون الأداء هو الشاغل الوحيد:

• LZO لديه رخصة GPL.
• liblzf لديه رخصة بي إس دي.
• miniLZO.tar.gz هذا هو LZO, ، تمت إعادة تجميعه للتو في إصدار "مصغر" أكثر ملاءمة للتطوير المضمن.

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

LZO, ، بخاصة miniLZO, ، و liblzf كلاهما ممتاز للأهداف المضمنة.

Answer 2

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

اعتمادًا على البيانات، سأجرب huffman برموز ثابتة أو lz77 (انظر روابط Brian).

Answer 3

حسنًا، الخوارزميتان الرئيسيتان اللتان تتبادران إلى ذهنك هما هوفمان و LZ.

الأول في الأساس يقوم فقط بإنشاء قاموس.إذا قمت بتقييد حجم القاموس بشكل كافٍ، فمن المفترض أن يكون سريعًا جدًا...ولكن لا تتوقع ضغطًا جيدًا جدًا.

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

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

Answer 4

نظرًا لأن هذا يبدو صوتًا، فسألقي نظرة على PCM التفاضلي أو ADPCM، أو شيء مشابه، مما سيقلله إلى 4 بتات/عينة دون خسارة كبيرة في الجودة.

مع تطبيق PCM التفاضلي الأساسي، ما عليك سوى تخزين فرق موقع بمقدار 4 بت بين العينة الحالية والمراكم، وإضافة هذا الاختلاف إلى المجمع والانتقال إلى العينة التالية.إذا كان الفرق خارج [-8,7]، فيجب عليك تثبيت القيمة وقد يستغرق الأمر عدة عينات حتى يتمكن المجمع من اللحاق بها.يتم فك التشفير بسرعة كبيرة دون استخدام أي ذاكرة تقريبًا، فما عليك سوى إضافة كل قيمة إلى المجمع وإخراج المجمع كعينة تالية.

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

إذا كان جهازك يحتوي على قانون μ غير خطي أو A-law ADC، فيمكنك الحصول على جودة مماثلة لـ 11-12 بت مع عينات 8 بت.أو ربما يمكنك القيام بذلك بنفسك في وحدة فك التشفير الخاصة بك. http://en.wikipedia.org/wiki/M-law_algorithm

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

Answer 5

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

Answer 6

لقد استخدمت zlib في الأنظمة المضمنة لمحمل التشغيل الذي يقوم بفك ضغط صورة التطبيق إلى ذاكرة الوصول العشوائي (RAM) عند بدء التشغيل.الترخيص متساهل بشكل جيد، وليس هراء GPL.إنه يقوم بإجراء مكالمة واحدة من malloc، ولكن في حالتي قمت ببساطة باستبدال هذا بكعب روتين يعيد مؤشرًا إلى كتلة ثابتة، وكعب روتين free() مناظر.لقد فعلت ذلك من خلال مراقبة استخدام تخصيص الذاكرة للحصول على الحجم الصحيح.إذا كان نظامك يمكنه دعم تخصيص الذاكرة الديناميكية، فسيكون الأمر أبسط بكثير.

http://www.zlib.net/