علوم رایانش و فناوری اطلاعات

بهینه‌سازی کدهای دودویی

نویسندگان

1 دانشکده علوم،دانشگاه شاهد، تهران، ایران

2 دانشکده علوم، دانشگاه شاهد، تهران، ایران

3 واحد تهران مرکزی، دانشگاه آزاد اسلامی، تهران، ایران

4 دانشکده علوم، دانشگاه مراغه، آذربایجان شرقی، ایران

چکیده

در این‌مقاله نشان داده شده است که می‌توان هر نوع داده دودویی را به‌صورت اجتماعی از کدکلمه‌هایی با طول متغیر تعریف کرد. این ویژگی به ما کمک می‌کند که بتوان نگاشتی یک‌به‌یک و پوشا از کدکلمه‌های پیشنهادی به کدکلمه‌های مورد نیاز تعریف کرد. از این‌رو با جایگزینی کدکلمه‌های جدید، داده‌های دودویی به داده‌های دودویی دیگری در راستای اهداف موردنظر تبدیل می‌گردد. یکی از این اهداف، کاستن حجم داده است. یعنی به‌جای کدکلمه‌های اصلی هر داده‌ی دودویی، کدکلمه‌های هافمن را جایگزین نمود تا حجم داده کمتر گردد. یکی از ویژگی‌های این‌روش، نتیجه‌ی فشرده‌سازی مثبت برای هر نوع داده‌ی دودویی است، یعنی صرف‌نظر از حجم جدول کد، تفاضل حجم داده‌ی اصلی و حجم داده بعد از فشرده‌سازی، بزرگتر یا مساوی صفر خواهد شد. ویژگی‌ مهم و کاربردی دیگر این‌روش، استفاده از کدکلمه‌های متقارن به‌جای کدکلمه‌های اصلی به‌منظور ایجاد خواص تقارن، بازگشت پذیری و مقاومت در برابر خطا با قابلیت کدگشایی دوطرفه است.

کلیدواژه‌ها

  • [1] A. Jones and J. M. Jones, “Information and coding Theory,” Springer, New York, 2012.
  • [2] X. Ruan and R. Katti, Department of Electrical and Computer Engineerin “Reducing the Length of Shannon-Fano-Elias Codes and Shannon-Fano Codes”, Military Communications Conference and MILCOM IEEE, 2006.
  • [3] H. Narimani, M. Khosravifard, and T. A. Gulliver, “How suboptimal is the Shannon code?” IEEE Trans. Inf. Theory, vol. 59, no. 1, pp. 458–471, Jan. 2013.
  • [4] J. Berstel and D. Perrin, “Theory of Codes,” Orlando: Academic Press, 1985.
  • [5] D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proc. IRE, vol. 40, no. 9, pp. 1098–1101, Sep. 1952.
  • [6] T. M. Cover and J. A. Thomas, “Elements of Information Theory,” 2nd ed. Hoboken, NJ, USA: Wiley, 2006.
  • [7] X. Zheng, Y. Lan, Y. Zhang, “A Two Stage Pipeline CAVLC Implementation for H.264/AVC,” Journal of Information & Computational Science, pp. 995-1002, 2008.
  • [8] T. Cover, “Enumerative source encoding,” IEEE Information Society Theory, Vol. 19, pp. 73 –77, Issue. 1, January 1973.
  • [9] H.S. Cronie, S.B. Korada “Lossless sourc 2211e coding with polar codes,” IEEE International Symposium on Information Theory, July 2010.
  • [10] G. Dudek. P. Borys and J. Grzywn, “Lossy dictionary-based image compression method,” Journal of Image and Vision Computing. Vol. 25, P. 883–889, 2007.
  • [11] KH. Sayood, “Introduction to Data Compression,” Elsevier. Murgan Kuafman Publisher,” 2006.
  • [12] S. Verd´ and u. Teaching IT, “XXVIII Shannon Lecture,” in Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT’07), 2007. 4
  • [13] Sh. Porwal, Y. Chaudhary, J, Joshi and M, Jain, Department of Computer Science and Engineering Vedaant Gyan Valley, Village Jharna, Mahala – Jobner and Link Road, “Data Compression Methodologies for Lossless Data and Comparison between Algorithms,” International Journal of Engineering Science and Innovative Technology (IJESIT). Vol. 2, Issue 2, 2013.
  • [14] W. Szpankowski and S. Verd´u, “Minimum Expected Length of Fixed-toVariable Lossless Compression Without Prefix Constraints,” IEEE Trans. Inform. Theory, Vol. 57, pp. 4017–4025, 2011.
  • [15] W. Szpankowski, “A One-to-One Code and its Anti-Redundancy,” IEEE Trans. Inform. Theory, Vol. 54. pp. 4762–4766, Oct. 2008.
  • [16] X. Ruan and R. Katti, “Department of Electrical and Computer Engineerin. Reducing the Length of Shannon-Fano-Elias Codes and Shannon-Fano Codes,” Military Communications Conference and MILCOM IEEE, 2006.
علوم رایانش و فناوری اطلاعات
دوره 19، شماره 1
بهار و تابستان
اردیبهشت 1400