Designing and Implementing a Self-checking Bubble sort Utilizing Dong’s Code Methodology

AMAL J. MAHFOUD; AML F. ELLAFI

doi:10.58916/jhas.v10i3.919

المؤلفون

AMAL J. MAHFOUD مؤلف
AML F. ELLAFI Department of Computer Engineering ,College of Electronic Technology, Bani Walid, Libya مؤلف

DOI:

https://doi.org/10.58916/jhas.v10i3.919

الكلمات المفتاحية:

Dong's Code، Bubble Sort، Information Redundancy، Concurrent Error Detection (CED)، Self-checking, VHDL

الملخص

Traditional Bubble Sort is prone to undetected errors due to lacking built-in error detection. This paper presents a self-checking Bubble Sort algorithm using Dong's Code methodology and information redundancy for concurrent error detection (CED). The design incorporates runtime assertions, invariant checks, and parity-based validation to guarantee immediate identification of sorting errors, significantly improving algorithmic reliability. Implemented in VHDL and validated through functional and fault-injection simulations using Active-HDL, the architecture demonstrates robust fault tolerance with low overhead (18.2-34.7% area penalty, ≤3-cycle latency) across small-to-medium datasets (n=8 to n=32). Applications needing high integrity, like real-time systems and safety-critical embedded controllers, benefit from its error-resilience while maintaining algorithmic simplicity.

التنزيلات

تنزيل البيانات ليس متاحًا بعد.

السيرة الشخصية للمؤلف

AMAL J. MAHFOUD
Personal and contact information

Full Name: Amal Jumah Millad

Nationality: Libyan

E-mail: amal_11081@yahoo.com

Educational background

2010 Master of Science M.Sc in Computer Engineering and lnformation Technology,Academy of Graduate Studies,Tripoli-Libya.

2003 Bachelor of science B.Sc in computer engineering, The Higher Institute of Electronics, Bani Walid Libya

Languages:

Arabic language; mother tongue language

English language; V.Good

Work experience:

2004-2006       Teacher of Computer sciences, Secondary school, Bani Walid Libya

2010-2020       One of the staff members in Computer Department, College of

Electronic Technology, Bani Walid Libya



2021                Assistant Professor in Computer Department, College of

Electronic Technology, Bani Walid Libya

Taught Courses:

Digital Design.

Introduction to computer.

Computer Circuit Design.

Computer Architecture.

Introduction in VHDL.

Parallel processing .

Fault tolerance .

Computer Languages:

C&C++ -Visual Basic- VHDL

List of Selected Publications:
- Amal J.Mahfoud,and Ali H.Maamar, "Self Checking FIFO Queue",2010 Int.conf.on Computer Technology and Development ( ICCTD 2010),Cairo,Egypt,November 2-4,2010.
- Amal J. Mahfoud, Khadija F. Omran, and Ali H. Maamar, “Design of a Self Checking Up-Down Counter”, 12^th WSEAS International Conference on Applied Information and Communication, Advances in Applied Information, August 21-23,2012, Istanbul, Turkey.
- Khadija F. Omran, Amal J. Mahfoud, and Ali H. Maamar, “Design of a Self Checking Up Counter”, (ICACELT 2013) International Conference on Advanced Computing, Engineering & Learning Technologies, September 15-16, 2013, ABU DHABI, UAE.
- Amal J. Mahfoud, Khadija F. Omran, and Ali H. Maamar, “Design of a Self Checking Down Counter”, Libyan International Conference on Electrical Engineering and Technologies (LICEET2018) , 3 – 7 March 2018, Tripoli - Libya.
- Khadija F. Omran, Amal J. Mahfoud, Ali H. Maamar, and Khaled M. Alnegrat “Self-Checking Decoder Using Hardware Redundancy”, Journal of Electrical, Electronic Engineering and Information Technology.Vol. 1, Issue 1 July 2020.

المراجع

D. A. Anderson, “Design of Self-Checking Digital Networks Using Coding Techniques,” CSL/Univ. Illinois, Urbana, 1971.

Husayn Abo showfa , Osama A Alhashi, Alhadi A Khallefah, Abobakar B Zargoun,”Self-Checking Bubble Sort using Berger Code”, International Journal of Innovative Research in Science, Engineering and Technology (IJIRSET), Volume 12, Issue 2, February 2023

Michael Nicolaidis, “Carry Checking/Parity Prediction Adders and ALUs”, IEEE Transactions On Very Large Scale Integration (Vlsi) Systems, Vol. 11, No. 1, February 2003

R. Leveugle et al., "Fault-Tolerant Architectures for VLSI Sorting Networks", IEEE Trans. on VLSI, vol. 26, pp. 112-125, 2018.

Russell, G., and Maamar, A.H., "Check bit prediction scheme using Dong's code for concurrent error detection in VLSI processors," Computers and Digital Techniques, IEE Proceedings - vol.147, no.6, pp.467-471, Nov 2000.

Hao Dong, “Modified Berger Code for Detection of Unidirectional Errors”, Computers, IEEE Transactions on, vol. c-33, no.6, pp.572-575, June 1984.

Maamar, A.H., and Russell, G. “A 32-bit RISC processer with concurrent error detection” Pro. 24th Euromicro Conference, August 1998, Sweden, pp.461-467.

Amal J. Mahfoud, Khadija F. O. Algheitta, Kareema G.Milad,” Design of a Self Checking Shift Right Register using Dong’s Code”, Almaarefah journal for humanities and applied sciences seventh Issue– June 2022.

Parag K. Lala, "Self Checking and Fault tolerance digital Design",Morgan Kaufmann Publisher, 2001.

Russell, G. and Elliot, I.D., “Design of Highly Reliable VLSI Processors Incorporating Concurrent Error Detection and Correction ” , Proceedings EURO ASIC91, May 1991 Paris .

Mohamed A. Abufalgha , “Self-Checking Cache Memory: Enhancing Reliability and Error Detection in digital Systems” ,Al-satil Vol. 17 No. 35 September 2023.

Miron Abramovici, Melvin A.Breuer, and Arthur D.Friedman, "Digital Systems Testing and Testable Design”,1990,ISBN 0-7803- 1062-4, Chapter 13:SELF-CHECKING DESIGN, pp.569-587.

Huda Abugharsa, and Ali Maamar," Self Checking Systolic LIFO Stack",7th WSEAS Int. Conf. on Instrumentation, Measurement, Circuits and Systems (IMCAS '08), Hangzhou, China, April 6-8,2008.

T. Chen & M. Patel, "Real-Time Monitoring Frameworks for Resilient Sorting Architectures," ACM Trans. Embed.Comput.Syst.,vol.23,no.2,Apr.2024.

R. Al-Saedi et al., "Real-Time Anomaly Detection in Hardware Sorters Using Adaptive Monitoring," J. Parallel Distrib. Comput., vol. 183, Jan. 2024.

Martin Omana, Daniele Rossi, Cecillia Metra, "Low Cost and High Speed Embedded Two-Rail Checker", IEEE Transaction on Computer, Vol.54, No.2, February 2005, pp.153-164

R. Vemuri et al., "Waveform-Driven Performance Analysis of Fault-Tolerant Sorters" IEEE Trans. Comput.-AidedDes.,vol.42,no.11,pp.3897–3908,2023.

K. Patel & L. Zhang, "Waveform-Driven Verification of Fault-Tolerant Sorting Architectures," IEEE Trans. VLSI,vol.31,no.5,pp.712–725,May2024.

T. Chen & M. Patel, "Linear-Time Sorting Frameworks for FPGA-Accelerated Edge Computing," ACM Trans. Embed. Comput. Syst., vol. 23, no. 2, Apr. 2024.