شناسایی و تشخیص خطا در محاسبات دی ان ای مبتنی بر مدل ادلمن-لیپتون

محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسی

فرزانه فاموری ¹ , امیر صباغ ملاحسینی ² , آزاده سادات عمرانی زرندی ³

1 - PHD student of Islamic Azad University, Kerman Branch- Faculty Member of Islamic Azad University, Zahedshahr Branch
2 - گروه مهندسی کامپیوتر - دانشگاه آزاد اسلامی واحد کرمان
3 - Department of Computer Engineering, Shahid Bahonar University of Kerman, Kerman, Iran

تاریخ دریافت : 1402/11/16 تاریخ پذیرش : 1403/03/26 تاریخ انتشار : 1403/05/24

کلید واژه: محاسبات DNA, سیستم اعداد مانده‌ای افزونه (RRNS), تشخیص خطا, تصحیح خطا,

چکیده مقاله :

محاسبات DNA حوزه ای از محاسبات طبیعی است و بر اساس این ایده است که فرآیندهای زیست شناسی مولکولی می تواند برای اعملیات حسابی و منطقی روی اطلاعات رمزگذاری شده به عنوان رشته های DNA استفاده شود. DNA معمولاً در لوله‌های آزمایشی که مستعد خطا هستند محاسبه می‌شود. سیستم عددی منطبق شده برای سادگی و قابلیت اطمینان فرایندهای محاسباتی DNA حائز اهمیت است. سیستم اعداد مانده‌ای انتخاب خوبی برای قابل‌اعتماد کردن و کارآمدتر کردن عملیات محاسباتی DNA است. قابلیت‌های سیستم تشخیص و تصحیح خطای RNS را می‌توان برای محاسبات DNA مستعد خطا به کار برد. در این مقاله، یک سیستم محاسباتی DNA را بر اساس سیستم اعداد مانده ای افزونه (RRNS) پیشنهاد شده است. این سیستم می تواند دو خطا را تشخیص و یک خطا را نیز تصحیح کند. مدل ادلمن-لیپتون برای انجام عملیات DNA با قابلیت تشخیص و تصحیح خطا استفاده شده است. مزیت این سیستم محاسباتی پیشنهادی توانایی تشخیص و تصحیح خطاها است. با این حال، عملیات محاسباتی پیشنهادی روی اعداد بزرگتر ارائه شده توسط DNA کار می کند، که RNS این اعداد را به اعداد کوچکتر تقسیم می کند. اجرای عملیات حسابی بر روی این اعداد کوچک، احتمال خطا در عملیات DNA را کاهش می دهد.

چکیده انگلیسی:

DNA computing is an area of natural computing based on the idea that molecular biology processs can be used to arithmetic and logical operations on information encoded as DNA strands. DNA is typically computed in test tubes that are prone to error, The RNS error detection and correction capabilities can be applied for error-prone DNA computing. In this work , we propose a DNA computing system based on Redundency Residue Number System (RRNS). While the system can detect two errors it is also able to correct an error. The Adleman-Lipton model is used to implement DNA operations with error detection and correction capability. The advantage of this proposed computing system is the ability to detect and correct errors. However, the proposed arithmetic operations work on larger numbers DNA-represented ,that RNS split these numbers into smaller numbers. Implementing of arithmetic operations on these small numbers reduces the possibility of errors in DNA operations.

منابع و مأخذ:

[1] H. M. H. Babu. "Multiple-Valued Computing in Quantum Molecular Biology: Arithmetic and Combinational Circuits". CRC Press, 2023.
[2] S. Minocha, S. Namasudra. "Research challenges and future work directions in DNA computing." Advances in Computers 129 (2023): 363-387.
[3] C. Zhang, G. Lulu, Z. Yuchen, S. Ziyuan,Z. Zhiwei, Zaichen, Y. Xiaohu You. "DNA computing for combinational logic." Science China Information Sciences 62 (2019): 1-16.
[4] F. Hochella, M., "There’s plenty of room at the bottom: Nanoscience in geochemistry," Elsevier, 2001.
[5] L. M. Adleman. "Molecular computation of solutions to combinatorial problems. Science", 266(5187), 1021-1024, 1994
. [6] L. Sousa. "Nonconventional computer arithmetic circuits, systems and applications." IEEE Circuits and Systems Magazine 21, no. 1 (2021): 6-40
. [7] CH. Chang, A. Sabbagh Molahosseini, A. Emrani Zarandi, TF. Tay, "Residue Number Systems: A New Paradigm to Data path Optimization for Low-Power and High-Performance Digital Signal Processing Applications," IEEE Circuits and systems magazine, vol. 15, no. 4, pp. 26-44, 2015
. [8] B. Yurke, A. J. Turberfield, A.P. Mills Jr, F. C. Simmel, J. L. Neumann, "A DNA-fuelled molecular machine made of DNA," Nature, vol. 406, no. 6796, pp. 605-608, 2000
. [9] X. Zheng, B.Wang, C. Zhou, X. Wei, Q. Zhang, "Parallel DNA Arithmetic Operation With One Error Detection Based on 3-Moduli Set," IEEE transactions, vol. 15, no. 5, pp. 499-507, 14 June 2016
[10] X. Zheng, J. Xu, W. Li, "Parallel DNA arithmetic operation based on the n-moduli set," Applied Mathematics and Computation, vol. 212, no. 1, Jun 2009, pp. 177-184
. [11] F. Famoori, A. Sabbagh Molahosseini. A, and A. Alsadat Emrani Zarandi. "DNA Arithmetic With Error Correction." IEEE Transactions on NanoBioscience 22.2 (2022): 329-336
. [12] M. Sarkar, P Ghosal, SP Mohanty, "Exploring the Feasibility of a DNA Computer: Design of an ALU using Sticker Based DNA Model," IEEE Transactions on Nanobioscience, vol. 16, no. 20, pp. 383-399, 2017
. [13] A. Fujiwara, KI. Matsumoto, W. Chen, "Procedures for logic and arithmetic operations with DNA molecules," International Journal of Foundations of Computer Science, vol. 15, no. 3, 2004
. [14] A. Molahosseini, L. Sousa, C. Chang (Eds), “Embedded Systems Design with Special Arithmetic and Number Systems”, Springer, 2017
. [15] L Sousa, S Antao, P Martins, “Combining Residue Arithmetic to Design Efficient Cryptographic Circuits and Systems”, IEEE Circuits and Systems Magazine, 16 (4), pp. 6-32, 2016
. [16] F. J. Taylor, "Residue Arithmetic A Tutorial with Examples," IEEE Computer, vol. 17, no. 5, pp. 50–62, 1984
. [17] EB Olsen, "Introduction of the Residue Number Arithmetic Logic Unit with Brief Computational Complexity Analysis (Rez-9soft processor)," Whitepaper, Digital System Research 2015
. [18] Ds. Anderson, "Design and Implementation of an Instruction Set Architecture and an Instruction Execution Unit for the REZ9 Coprocessor System," M.S. Thesis, U of Nevada LV, 2014
. [19] K. Navi, A. Sabbagh Molahosseini. M. Esmaeildoust, "How to Teach Residue Number System to Computer Scientists and Engineers," IEEE Transactions on Education, vol. 54, no. 1, pp. 156-163, 2011
. [20] T. F. Tay and C. H. Chang, "A non-iterative Multiple Residue Digit Error Detection and Correction Algorithm in RRNS,” IEEE Transactions on Computers, vol. 65, no. 2, pp. 396-408, February 2016
[21] F. Guarnieri, M. F. Liss, C. Bancroft, "Making DNA add," Science, vol. 273, no. 5272, pp. 220-223, 1996
. [22] A. Fujiwara, S. Kamio," Procedures for Multiple Input Functions with DNA strands," Journal of Foundations of Computer Science 2005
. [23] W. Wang, M. N. S. Swamy, and M. Omair Ahmad. "Moduli selection in RNS for efficient VLSI implementation." 2003 IEEE International Symposium on Circuits and Systems (ISCAS). Vol. 4. IEEE, 2003
. [24] A. Sabbagh Molahosseini, K.Navi, C. Dadkhah, O. Kavehei, S. Trimarchi, "Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n–1, 2n, 2n+1, 22n+1–1} and {2n–1, 2n+1, 22n, 22n+1} Based on New CRTs," IEEE Transactions on Circuits and Systems-I, vol. 57, no. 4, pp. 823-835, 2010
. [25] B. Deng, S. Srikanth, E. R. Hein, T. M. Conte, E. Debenedictis, Je. Cook, M.P. Frank, "Extending Moore’s Law via Computationally Error Tolerant Computing," ACM Transactions on Architecture and Code Optimization (TACO), vol. 15, no. 1, 2018
. [26]
https://www.xlnsresearch.com/sticker1.htm

متن کامل:



	دوره هفدهم، شماره بهار و تابستان 1403   مجله فناوری اطلاعات در طراحی مهندسی Information Technology in Engineering Design https://sanad.iau.ir/journal/ited
شناسایی و تشخیص خطا در محاسبات دی‌ان‌ای مبتنی بر مدل ادلمن-لیپتون فرزانه فاموری(1)     امیر صباغ ملا حسینی*(2)     آزاده سادات عمرانی زرندی(3)   (1)       گروه مهندسی کامپیوتر، واحد کرمان، دانشگاه آزاد اسلامی، کرمان ایران  (2)       گروه مهندسی کامپیوتر، واحد کرمان، دانشگاه آزاد اسلامی، کرمان ایران* (3)       گروه مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان، کرمان، ایران    (تاریخ دریافت :16/11/1402     تاریخ پذیرش:26/03/1403)
چکیده  محاسبات DNA حوزه‌ای از محاسبات طبیعی است و بر اساس این ایده است که فرآیندهای زیست‌شناسی مولکولی، می‌تواند برای عملیات حسابی و منطقی روی اطلاعات رمزگذاری‌شده به عنوان رشته‌های DNA استفاده شود. DNA معمولاً در لوله‌های آزمایشی که مستعد خطا هستند، محاسبه می‌شود. سیستم عددی منطبق‌شده، برای سادگی و قابلیت اطمینان فرایندهای محاسباتی DNA حائز اهمیت است. سیستم اعداد مانده‌ای، انتخاب خوبی برای قابل ‌اعتماد کردن و کارآمدتر کردن عملیات محاسباتی DNA است. قابلیت‌های سیستم تشخیص و تصحیح خطای RNS را می‌توان برای محاسبات DNA مستعد خطا به کار برد. در این مقاله، یک سیستم محاسباتی DNA را بر اساس سیستم اعداد مانده‌ای افزونه (RRNS) پیشنهاد شده است. این سیستم می تواند دو خطا را تشخیص و یک خطا را نیز تصحیح کند.  مدل ادلمن-لیپتون برای انجام عملیات DNA با قابلیت تشخیص و تصحیح خطا استفاده شده است. مزیت این سیستم محاسباتی پیشنهادی، توانایی تشخیص و تصحیح خطاها است. با این حال، عملیات محاسباتی پیشنهادی روی اعداد بزرگتر ارائه شده توسط DNA کار می کند، که RNS این اعداد را به اعداد کوچکتر تقسیم می کند. اجرای عملیات حسابی بر روی این اعداد کوچک، احتمال خطا در عملیات DNA را کاهش می دهد.   کلمات کلیدی: محاسبات DNA، سیستم اعداد مانده‌ای افزونه (RRNS)، تشخیص خطا، تصحیح خطا *عهده‌دار مکاتبات:                  امیر صباغ ملا حسینی         نشانی: گروه مهندسی کامپیوتر، واحد کرمان، دانشگاه آزاد اسلامی، کرمان ایران  پست الکترونیکی: [e-mail]

 

1-       مقدمه

محاسبات مولکولی یا محاسبات DNA (Deoxyribose Nucleic Acid) یکی از رشته‌های جدید علوم کامپیوتر است. این یک روش جدید برای محاسبات موازی انبوه است که می‌تواند در کسری از زمان به حل مسائل NP-کامل یا غیرقطعی چند جمله‌ای زمان بپردازد. مسائل ترکیبی، حوزه دیگری است که محاسبات DNA در آن برتری دارد. این ترکیبی عالی از بیوشیمی، زیست‌شناسی مولکولی و علوم کامپیوتر است که به محققان اجازه می‌دهد، عملیات‌های حسابی و منطقی را انجام دهند که محاسبات را با استفاده از مولکول‌های بیولوژیکی به جای پردازنده‌های سیلیکونی معمولی انجام می دهد]1[. محاسبات DNA یک زمینه نوظهور است که می‌تواند مسئول گسترش سایر فناوری‌های امیدوارکننده باشد. نقش حیاتی محاسبات DNA به دلیل ذخیره سازی بالا، کارایی انرژی و قابلیت‌های موازی در مقیاس بزرگ است. چنین قابلیت‌های امیدوارکننده‌ای تمرکز بسیاری از محققان را برای جایگزینی رایانه‌های سنتی، یعنی رایانه‌های مبتنی بر سیلیکون با رایانه‌های بیومولکولی، یعنی رایانه‌های مبتنی بر DNA، به خود جلب کرده است.  این کار چالش‌های بلادرنگ مختلفی را که محققان مختلف برای پیاده‌سازی محاسبات DNA در زمینه‌های کاربردی مختلف با آن مواجه هستند، مورد بحث قرار می‌دهد. این شامل چالش‌های مبتنی بر شیمی DNA، احتمال خطا و هزینه، مسائل ترکیبی و حالت محدود است. زمینه‌های کاری محاسبات DNA در آینده، قابلیت‌های آن را برای حل چالش‌های مختلف فناوری‌های عصر جدید مانند داده‌های بزرگ، محاسبات ابری، بلاک چین، محاسبات کوانتومی، نانوتکنولوژی و بسیاری دیگر نشان می‌دهد]2[. محاسبات DNA یک فناوری نوظهور است که می تواند بر محدودیت‌های فناوری محاسبات مبتنی بر سیلیکون به دلیل سرعت محاسبات بالا و قابلیت‌های موازی‌سازی غلبه کند]3[. 

 در سال 1961، فیزیکدان ریچارد فاینمن برای اولین بار ایده استفاده از سلول‌های زنده و مجموعه پیچیده مولکولی در ساخت کامپیوترهای میکروسکوپی را مطرح کرد. فاینمن درباره مشکل کار کردن و کنترل کردن اجزا در ابعاد و مقیاس کوچک بحث کرد و رشته نانوتکنولوژی را بنیان نهاد. اگر چه او به صورت عمده روی ذخیره اطلاعات و کار در سطح مولکولی تمرکز کرد، به پتانسیل سیستم‌های بیولوژیکی به عنوان پردازنده‌های اطلاعات در مقیاس کوچک اشاره کرد ]4[.  در سال 1994، ادلمن با رمزگذاری رئوس و لبه‌ها با استفاده از رشته‌های DNA، انجام یک سری عملیات مولکولی بر روی محلول  DNA و در نهایت رمزگذاری خروجی، مسئله هامیلتونی را در یک لوله آزمایش حل کرد ]5[.

بسیاری از تحقیقات پیرامون DNA امروزه به رفع مسائل تحقیقات ترکیبی جست‌وجو معطوف شده است. به‌هرحال برای اینکه محاسبات DNA در محدوده گسترده‌تری از مشکلات کاربرد داشته باشد، به عملیات ریاضی پایه از قبیل عملیات منطقی مثل AND، OR و NOT، و عملیات حسابی مثل جمع و تفریق، ضرب نیاز است که بتوان در طراحی ALU مبتنی بر DNA برای ساخت کامپیوترهای مولکولی از آن استفاده نمود. ریاضیات نقش مهمی در عملکرد و کارایی یک کامپیوتر بازی می کند. ساختن پلتفرم‌های محاسباتی جدید با پشتیبانی از محاسبات باینری سنتی و فن‌آوری‌های مبتنی بر سیلیکون برای برآورده کردن الزامات برنامه‌های امروزی، بدون توجه به اینکه دستگاه‌های تعبیه‌شده یا رایانه‌های با کارایی بالا را در نظر می‌گیریم، به طور فزاینده‌ای چالش برانگیز می‌شود. اگرچه محاسبات باینری با موفقیت برای طراحی سیستم‌های محاسباتی مبتنی بر سیلیکون استفاده شده است، ماهیت موقعیتی این نمایش، منجر به انتشار رقم نقلی می‌شود؛ که از قابلیت موازی‌سازی در ابتدایی‌ترین سطوح جلوگیری می‌کند و منجر به مصرف انرژی بالا می‌شود. از این رو، تحقیق بر روی یک سیستم‌ عددی برای کشف موازی‌سازی و بهره‌گیری از ویژگی‌های فناوری‌های نوظهور برای بهبود عملکرد و بازده انرژی سیستم‌های محاسباتی بسیار مورد توجه است ]6[.

در محاسبات  DNA، به دلیل تأثیر انتشار رقم نقلی، داشتن یک سیستم عددی که با اصول سادگی و موازی‌سازی در محاسبات DNA همسو باشد، مهم است. استفاده سیستم اعداد مانده ای (¹RNS) در عملیات ریاضی DNA باعث کارآمدی DNA می‌شود.  RNSبه طور بالقوه می‌تواند الزامات قابلیت اطمینان را با استفاده از ویژگی موازی‌سازی و عملیات حسابی پیمانه‌ای کاهش دهد. در این سیستم، محاسبات روی پیمانه‌ها به صورت جداگانه انجام می‌شود. اگر یکی از پیمانه‌ها خطا داشته باشد، اثر آن به پیمانه دیگر منتقل نمی‌شود و همچنین مشکل انتشار رقم نقلی را ندارد] 7[.  علاوه بر این،  DNA معمولاً در لوله‌های آزمایشی که مستعد خطا هستند محاسبه می‌شود و به دلایل ناشناخته مانند واکنش‌های بیوشیمیایی مثبت و منفی کاذب، ممکن است نتایج نادرستی رخ دهد ]9و8[. اگرچه انگیزه اولیه در مطالعات RNS اجرای عملیات محاسباتی سریع است، اما برخی از ویژگی‌های جالب مرتبط با این سیستم وجود دارد که آن را برای تشخیص و تصحیح خطا ایده‌آل می‌کند ]7[. قابلیت‌های تشخیص و تصحیح خطای RNS را می‌توان برای محاسبات DNA مستعد خطا به کار برد. برای اولین بار در]10[ روش‌های پیشنهادی برای انجام عملیات حسابی در RNS با استفاده از رشته‌های   DNA  ارائه شد. در ]9[ عملیات تشخیص فقط یک خطا مبتنی بر²RRNS برای محاسبات DNA انجام شده است. در مقاله ]11[  عملیات تشخیص و تخصیص خطا مبتنی برRRNS  برای محاسبات DNA برای تشخیص دو خطا و تصحیح یک خطا بر اساس مدل استیکر³ انجام داده‌ایم.

در اینجا یک سیستم محاسباتی DNAای پیاده‌سازی کرده‌ایم که قابلیت موازی‌سازی با سرعت بالا و قابلیت تحمل‌پذیری خطا مبتنی بر سیستم اعداد مانده‌ای را دارد. مشخصات و ویژگی‌های این سیستم به این صورت است. جهت انجام دستورات DNA از مدل آدلمن – لیپتون⁴  استفاده شده است. عملیاتی ریاضی که عملیات تشخیص و تصحیح خطا روی آنها انجام شده است، عمل جمع است. برای اینکه این سیستم بتواند دو خطا را تشخیص و یک خطا را تصحیح کند، از سیستم اعداد مانده‌ای افزونه با مجموعه پیمانه ۴تایی و محدوده دینامیکی 6n بیتی استفاده شده است که دوتای این پیمانه‌ها، پیمانه اطلاعاتی و دو تای دیگر پیمانه افزونه است که قادر به تشخیص دو خطا و تصحیح یک خطا هستند و نوع مجموعه پیمانه به‌صورت   استفاده شده است. این مقاله به شرح زیر سازمان‌دهی شده است: در بخش 2، مبانی مدل محاسباتی DNA و سیستم‌های  RNS، RRNS ارائه شده است. در بخش 3، مجموعه پیمانه پیشنهادی و الگوریتم تشخیص و تصحیح خطا بیان شده است. بخش 4، توابع و الگوریتم‌های جدید محاسبات DNA  با تشخیص و تصحیح خطا، برای مدل ادلمن-لیپتون ارائه می‌شود. در نهایت، ارزیابی کار پیشنهادی و بحث و نتیجه‌گیری تکمیلی در بخش 5 و6 بیان شده‌اند.

 

2-       پیش‌زمینه

در این بخش، مدل ادلمن-لیپتون به عنوان مدل محاسباتی در DNA و ریاضیات مبتنی بر RNS معرفی شده‌اند.

 

2-1- اصول محاسبات DNA

یک رشته از DNA به عنوان یک رشته از چهار نوکلئوتید پایه مختلف تعریف می‌شود. چندین مدل برای محاسبات   DNA  پیشنهاد شده است]12[. لوله آزمایش T مجموعه‌ای از توالی‌های DNA بر اساس حروف الفبای (A, G, C, T) است. برخی از عملیات اساسی DNA پیشنهاد شده توسط آدلمن و لیپتون به صورت زیر انجام می شوند ]10[:

      ادغام (Merge): با دادن دو لوله‌ آزمایش   و  ، عمل   الحاق  را در  ذخیره می‌کند.

       کپی (Copy): با دادن لوله ‌آزمایش   ، عمل  یک لوله آزمایش   را با همان محتویات   تولید می‌کند.

       کشف (Detect): با دادن لوله ‌آزمایش  ، خروجی عمل  مقدار yes هست اگر T شامل حداقل یک رشته DNA  باشد در غیر اینصورت مقدار خروجی برابر no می‌باشد.

   جداسازی (Separation): با دادن لوله ‌آزمایش   و یک مجموعه رشته‌های X،  همه تک رشته‌ها که شامل زیررشته X باشد را، از  حذف می‌کند و یک لوله آزمایش  که شامل رشته‌های حذف شده باشد، تولید می‌کند.

  انتخاب (Selection): با دادن لوله ‌آزمایش   و یک عدد صحیح L،  تمام رشته‌های درون لوله آزمایش  که طولشان کمتر یا مساوی L باشد را حذف کرده و درون لوله آزمایش  قرار می‌دهد. 

  شکافتن (Cleavage): با دادن لوله ‌آزمایش T  و یک ‌رشته با دو سمبل ،  هر رشته دوتایی درون T که شامل  است را به دو تا رشته دوتایی به‌صورت زیر برش می‌دهد.

و فرض بر این است که این عملگر روی الفبای ∑  عمل می‌کند.

  ترکیب یا ساختن (Annealing):  با دادن لوله ‌آزمایشT ،  همه دو رشته‌ای‌های ممکن از ترکیب تک رشته‌هایی که درون T هستند را می‌سازد و این دو رشته‌ای‌های جدید در همان لوله‌ آزمایش T ذخیره می‌شوند.

 تفکیک‌کردن (Denaturation): با دادن لوله ‌آزمایشT ، هر دو رشته‌ای درون T را به دو تک رشته تبدیل می‌کند.

      خالی کردن Empty (T): با دادن لوله‌آزمایشT ،  لوله Tرا خالی می‌کند.

 

9 عملگر معرفی شده در بالا با تعداد ثابتی از مراحل بیولوژیکی برای رشته‌های DNA پیاده‌سازی شده‌اند. در اینجا فرض می‌شود که پیچیدگی هر عملگر O(1) مرحله آزمایشگاهی است و پیچیدگی تقریبی از ترتیبی از عملگرها در نظر گرفته می‌شود ]13[. .

 

2-2- RNS  و RRNS

انتشار رقم نقلی در سیستم عدد دودویی معمولی یک چالش اصلی جهت انجام عملیات ریاضی سریع است و به عنوان یک انگیزه کلیدی به کار برده شد؛ جهت اینکه این سیستم با سیستم عدد مانده‌ای جایگزین شود که در آن عملیات روی هر پیمانه به طور مستقل و موازی انجام می‌شود و مشکل انتشار رقم نقلی را ندارد [15و14].

سیستم اعداد مانده‌ای یک سیستم عددی غیروزنی هست که از مجموعه‌ای از اعداد صحیح مثبت پیمانه‌ها  (m1, m2 , … , mn) که دوبه‌دو نسبت به هم اول هستند تشکیل شده است  یعنی gcd (mi , mj)=1 برای . یک عدد وزندار X می‌تواند به صورت  نمایش داده می‌شود به‌طوری‌که:

(1)

چنین نمایشی برای هر عدد صحیح  X در محدوده  [0 , M-1] منحصربه‌فرد است، به‌طوری‌که M محدوده دینامیکی مجموعه پیمانه‌های  است و برابر است با حاصل‌ضرب miها   یعنی  ]16[.

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

یک مبدل مستقیم، شامل تبدیل کننده‌های مستقل برای هر پیمانه از مجموعه پیمانه می‌باشد که یک عدد دودویی صحیح وزندار را به عدد سیستم اعداد مانده‌ای معادلش تبدیل می‌کند. محاسبه باقی‌مانده در هر پیمانه به صورت جداگانه انجام می‌شود. این مبدل نسبت به مبدل معکوس، دارای طراحی آسان و پیچیدگی کمتری می باشد. بعد از اینکه نمایش مانده‌ای از عدد وزن‌دار توسط مبدل مستقیم به‌دست آمد، می‌توان عملیات حسابی مانند جمع، ضرب و تفریق را بر روی هر کدام از پیمانه‌ها به‌صورت مجزا و موازی انجام داد. نتیجه به‌دست‌آمده به یک مبدل معکوس انتقال می‌یابد تا به معادل دودویی تبدیل شود. عملیات حسابی در سیستم اعداد مانده‌ای بسیار سریع‌تر و ساده‌تر است. به دلیل این که باقی‌مانده‌ها نسبت به عدد اصلی کوچک‌تر هستند و به‌صورت مستقل انجام می‌شوند. در واقع سرعت انجام عملیات حسابی هنگامی که پیمانه‌ها کوچک باشند، بسیار بالا خواهد بود. هر پیمانه در مجموعه پیمانه پردازنده حسابی خودش را دارد که شامل پیمانه‌های جمع، تفریق و ضرب می‌باشد. بنابراین سیستم اعداد مانده‌ای شامل سه بخش مبدل مستقیم⁵، کانال پیمانه ای  یا واحد حساب و مبدل معکوس⁶ می‌باشد [19].

 

 

شکل 1: بلوک دیاگرام یک سیستم نمونه  RNS[19]

 

در سیستم اعداد مانده‌ای، با اضافه کردن پیمانه‌های افزونه به مجموعه پیمانه‌های موجود می‌توان سیستمی داشت که دارای قابلیت تشخیص و تصحیح خطا باشد که به آن سیستم اعداد مانده‌ای افزونه یا RRNS گفته می‌شود. یک سیستم اعداد مانده‌ای افزونه، n = k+r پیمانه اول  و یک محدوده دینامیکی دارد. به پیمانه‌های اضافه‌شده mk+ پیمانه افزونه گفته می‌شود و در مقابل به پیمانه‌های m1, m2, … , mk پیمانه اطلاعات گفته می‌شود. به فاصله  مربوط به k رقم مانده‌ای اطلاعات از مجموعه  nتائی محدوده قانونی و به فاصله  با توجه ‌به r رقم مانده‌ای افزونه ، محدوده غیرقانونی گفته می‌شود. محدوده قانونی، محدوده محاسباتی مفید سیستم عددی را نشان می‌دهد؛ درحالی‌که محدوده غیرقانونی، برای تشخیص خطا و سرریز مفید است. تعداد خطاهای قابل کشف و تصحیح بستگی به تعداد پیمانه‌های افزونه اضافه‌شده دارد. با r پیمانه افزونه، یک سیستم اعداد مانده‌ای افزونه قادر به تشخیص r و تصحیح   خطا می‌باشد. در نمایش باقیمانده‌ای همان‌طور که عملیات ریاضی پیمانه‌ای روی عملوندها در حال انجام هست؛ RRNS می‌تواند خطاهای حاصل از عملیات ریاضی را اصلاح کند. همچنین در RRNS باقی‌مانده‌ها مستقل از یکدیگر هستند، که باعث می‌شود خطای باقی‌مانده در یک کانال پیمانه به کانال‌های دیگر منتقل نشود. بنابراین، خطاهای وارد شده به رقم باقی‌مانده تنها اثر محلی دارند[7].

 شکل 2، یک مثال عددی از یک RNS با پیمانه‌های (3و5) و یک RRNS با پیمانه‌های (17و16و3و5) را نشان می‌دهد. 3 و 5 پیمانه اطلاعات و 16و 17 پیمانه افزونه می‌باشند. 2 و 5 هم دو عدد صحیح هستند که باقی‌مانده‌های آن‌ها با مبدل مستقیم به صورت ( 2،2،2،2) و (0،2،5،5) به ترتیب می‌باشند. عملیات ریاضی روی باقی‌مانده‌های این دو عدد در هر پیمانه به صورت مستقل انجام می‌شود. نتایج این عملیات تبدیل به عدد صحیح توسط الگوریتم مبدل معکوس می‌شود. در این مثال از CRT جهت انجام مبدل معکوس استفاده می‌شود. مراحل محاسباتی برای تبدل معکوس نتایج جمع، تفریق و ضرب برای سیستم RNS در این شکل نشان داده شده است. ارقام افزونه در RRNS می‌توانند برای تشخیص خطا استفاده شود. فرض کنید که یک اشکال در عمل جمع اتفاق می‌افتد و رقم مانده‌ای حاصل جمع در پیمانه دوم از 1 به 3 تغییر یابد. با در نظر گرفتن پیمانه افزونه به CRT عدد 2727 از مبدل معکوس به‌دست می آید که خارج از محدوده قانونی15 M=  (حاصل‌ضرب پیمانه‌های اطلاعات) می‌باشد. به این طریق خطا تشخیص داده شد؛ چون اینRRNS فقط یک پیمانه افزونه دارد بنابراین فقط یک خطا را می‌تواند تشخیص دهد. برای تصحیح این خطا RRNS باید حداقل دو پیمانه افزونه داشته باشد [20و7].

 

شکل2 : مثالی از محاسبات در RNS و RRNS

 

 

2-3- DNA و RNS

1)       نمایش اعداد باینری و صحیح مانده ای با رشته های DNA  در مدل ادلمن-لیپتون

در [13] یک نمایش DNA از اعداد باینری ارائه شده است. به‌طوری‌که یک رشته تکی DNA برای نمایش یک بیت استفاده می‌شود. نمایش m عدد باینری n بیتی مشابه [8] در اینجا نشان داده شده است. الفبای  و نمایش عدد به صورت زیر تعریف می‌شود:

                                 

(2)

 

     در (3)، A آدرس عدد و B موقعیت بیت را مشخص می‌کنند و در عملیات برش به‌کار برده می‌شوند. سمبل های 0 و1  مشخص‌کننده مقدار هر بیت می‌باشند و "#" برای عملیات جداسازی استفاده می‌شود. با استفاده از الفبای بالا مقدار یک بیت، به ‌وسیله یک رشته تکی به صورت زیر نمایش داده می‌شود که i آدرس و j موقعیت بیت را مشخص می‌کنند:

(3)

  به‌طوری‌که  اگر مقدار بیت صفر باشد، در غیر اینصورت .

 در [12و9] نمایش‌های DNA، m عدد صحیح n  بیتی در RRNS یه صورت زیر ارائه شده‌اند.

(4)

هر سمبول در  یک بخش از رشته تکی DNA را مشخص می‌کند. برای مجموعه پیمانه 4 تایی  ، هر عدد باقی‌مانده در محدوده دینامیکی به ‌وسیله یک مجموعه چهارتایی به صورت  نمایش داده می شود؛ که  و  یک رشته حافظه نامیده می‌شود. در این نمایش، i اندیس عدد در محدوده دینامیکی (کدامین عدد)، l موقعیت رقم باقی‌مانده و j موقعیت بیت، و V مشخص‌کننده مقدار بیت 0 یا 1 می‌باشد و سمبول‌های دیگر در مجموعه الفبای   برای عملیات Cleavage  و Separation استفاده می‌شوند. بنابراین یک رشته حافظه بر اساس الفبای  به صورت زیر ساخته می‌شود:

(5)

 

برای مثال، عدد صحیح ۵ در سیستم اعداد مانده‌ای با نمایش (0,2,5,5) به ‌وسیله 4 مجموعه رشته‌های تکی DNA  به‌صورت زیر نمایش داده می‌شود که در چهار لوله زیر ذخیره می‌شوند.

 

 

 

 

 

2)       عملیات اولیه مبتنی بر DNA

با استفاده از عملیات اساسی DNA چندین تابع برای ریاضیات مبتنی بر DNA و RNS تعریف شده‌اند. با توجه به مدل ادلمن- لیپتون توابع پایه‌ای به صورت زیر هستند:

تابع ValueAssignment ( , ) [10و8] : یک مقدار جدید یکسان  را به بیت مورد نظر در همه رشته‌های حافظه در لوله ورودی  تخصیص می‌دهد و نتیجه در لوله  ذخیره می‌شود.

تابع  Leftshift (Tinput) [10]: این تابع برای انتقال اعداد استفاده می‌شود. برای یک عدد دودویی ، الگوریتم شیفت به چپ مقدار  را بر می‌گرداند. در ابتدا مقدار عدد دودویی a در یک ‌رشته حافظه درون تیوب ورودی به نام Tinput ذخیره می‌شود، بعد از انجام عملیات الگوریتم تیوب Tinput رشته حافظه‌هایی را ذخیره می‌کند که نتیجه a’ را نشان می‌دهند.

تابع ] LogicOperation (Tinput, L, Toutput)21[: این تابع عملیات منطقی را بین دو عدد باینری انجام می‌دهد. این تابع عمل منطقی که در لوله L تعریف شده است را روی جفت رشته‌ای که در لوله Tinput  قرار دارند اعمال می‌کند و نتیجه عملیات منطقی را در لوله Toutput ذخیره می‌کند.

تابع Binaryadd (T1, T2, Tsum) ]10 [: دو عدد باینری که در رشته حافظه T1, T2 ذخیره شده‌اند را به‌صورت دودویی با هم جمع کرده و نتیجه عمل جمع را در رشته حافظه Tsum ذخیره می‌کند.

تابع EX_OR_ multi_operand (Tinput) ]22 [: عملیات EXOR را روی n عدد باینری m  بیتی انجام می‌دهد که لوله Tinput حاوی n عدد ورودی m  بیتی که در رشته‌های حافظه ذخیره شده‌اند .

تابع  AND_multi_operand (Tinput) ]22 [: همانند تابع EXOR  عملیات AND را روی n عدد m بیتی انجام می‌دهد.

تابع RNSAdd () ]22 [: این تابع دو عدد مانده‌ای با مجموعه پیمانه m تایی را با هم جمع می‌کند.

 

3-       مجموعه پیمانه پیشنهادی و تشخیص و تصحیح خطا

1)       انتخاب مجموعه پیمانه

انتخاب مناسب مجموعه پیمانه، نقش مهمی در طراحی کارامد سیستم اعداد مانده‌ای ایفا می‌کند. از پارامترهای مهم برای به‌دست آوردن محدوده دینامیک بزرگ در سیستم اعداد مانده‌ای انتخاب مجموعه پیمانه و تعداد آن‌هاست. از طرفی انتخاب پیمانه و تعداد آن‌ها باید به گونه‌ای باشد که در ضمن فراهم آوردن محدوده نمایش بزرگ دارای سرعت محاسبات و همچنین پیچیدگی سخت‌افزاری مناسبی باشد. علاوه بر این هزینه و عملکرد پیمانه‌ها به شکل و تعداد پیمانه‌ها در مجموعه نیز بستگی دارد [23].  مجموعه پیمانه‌های خوش‌فرم و متعادل زیادی وجود دارند که برای انجام محاسبات مناسب می‌باشند ولی به دلیل ساختار مبدل معکوس ناکارامد دارای هزینه زیاد و تاخیر در انجام عملیات هستند. از میان مجموعه پیمانه‌های موجود که دارای قابلیت‌های موازی سازی، تحمل خطا، محدوده دینامیکی بالا و پیاده سازی سخت افزاری ساده که سازگار با ویژگی های DNA باشد و همچنین قابلیت تصحیح خطا داشته باشد، مجموعه پیمانه 4 تایی  برای کار ارائه شده در اینجا انتخاب شد ]24 [که محدوده دینامیکی بالایی با ساختار مبدل معکوس ساده دارد که این ساختار را می‌توان به طور موثر با DNA پیاده سازی کرد. این مجموعه پیمانه 6n بیتی شامل پیمانه‌های ساده و خوش‌فرم که دارای خصوصیات سرعت بالا و طراحی مبدل معکوس با هزینه کم می باشد. در این مجموعه پیمانه از مبدل معکوس CRT1 استفاده می‌شود که باعث عملکرد بالا می‌شود. این مبدل تاخیر تبدیل کم و نیازمندی سخت افزاری کمتری را دارد.

2)       تشخیص و تصحیح خطا بر اساس مجموعه پیمانه

با توجه ‌به مجموعه پیمانه چهارتایی  که دو پیمانه اول، جزء پیمانه اطلاعاتی و دو پیمانه دوم، جزء پیمانه افزونه می‌باشد، می توان تشخیص دو خطا و تصحیح یک خطا را انجام داد. جهت تشخیص و تصحیح خطا در اینجا از الگوریتم [25] استفاده شده است. که بر اساس الگوریتم بررسی سازگاری⁷ و گسترش پایه BEX⁸ عمل می‌کند که نیاز به سخت افزار زیادی نخواهد بود. این الگوریتم برای یک سیستم با دو پیمانه اطلاعاتی (m1, m2) و دو پیمانه افزونه (m3, m4)، برای هر عدد  X( < M=m1m2m3m4 ) به‌صورت زیر است [25].

مرحله ۱: مجموعه پیمانه M = {m1, m2, m3, m4} و X = (x1 , x2 , x3 , x4 ) به عنوان باقی‌مانده‌های انتقال یافته در نظر بگیرید که باید همان باقی‌مانده‌های اصلی X در صورت رخ ندادن خطا باشد.

مرحله ۲: عدد وزندار  باید با توجه به پیمانه‌های اطلاعاتی  {m1, m2}و باقی‌مانده‌های متناظر (x1 , x2) با استفاده از CRT1 به صورت محاسبه شود که در آن  معکوس ضربی  به پیمانه  است.

مرحله 3:  برای i=3,4 یعنی برای پیمانه‌های افزونه {m3, m4} محاسبه شود.

مرحله 4: اگر هر دو  برابر با صفر باشند، هیچ خطایی وجود ندارد و همه باقی‌مانده‌ها صحیح هستند. در غیر این صورت، اگر تنها یک  غیر صفر هست، یک خطا در باقی‌مانده افزونه وجود دارد و به مرحله 5 برو. اگر هر دو  غیر صفر باشند، یک خطا در بخش اطلاعاتی وجود دارد و سپس به مرحله 6 برو.

مرحله 5: اگر  غیر صفر هست، پس  صحیح نیست، که با جای‌گذاری آن با  تصحیح می‌شود.

مرحله 6: پیمانه‌های افزونه را با پیمانه‌های اطلاعاتی جابه‌جا کن سپس  و  را برای i=3,4  محاسبه کن. اگر هر دو  غیر صفر هستند یعنی چندین خطا وجود دارد، در غیر این صورت اگر فقط یک  غیر صفر باشد، سپس   با  جایگزین شود.

پیاده‌سازی این الگوریتم با دو مثال به صورت زیر شرح داده می‌شود:

اولین مثال تصحیح یک خطا در پیمانه افزونه را نشان می‌دهد، در حالی که دومین مثال وجود خطا در پیمانه اطلاعاتی را نشان می‌دهد. عدد X=10 را در نظر بگیرید که نمایش با توجه به مجموعه پیمانه (17، 16، 3، 5) به صورت (10، 10، 1، 0) می‌باشد در حالی که 3 و 5 پیمانه اطلاعاتی و 16 و 17 پیمانه افزونه هستند.

در مثال اول فرض کنید که r3 از مقدار 10 به مقدار 3 تغییر کرده است (یعنی خطا دارد)، به طوری که کد دریافت‌شده به صورت x'= (0, 1, 3, 10) است. مراحل انجام این الگوریتم به صورت زیر می‌باشد:

(6)

مرحله 4: با توجه به اینکه  ، بنابراین یک خطا در بخش افزونه وجود دارد.

مرحله 5: بنابراین  صحیح نمی باشد و دارای خطا هست. برای تصحیح   با جایگزین می‌شود، به این صورت x'= (0, 1, 10, 10).

در مثال دوم، فرض کنید که r1 از مقدار 0، به مقدار 2 تغییر کرده است (یعنی خطا دارد). به طوری که کد دریافت شده به صورت x'= (2, 1, 10, 10) است. مراحل انجام این الگوریتم به صورت زیر می‌باشد:

مرحله 2:
مرحله 3:	,

مرحله 4: با توجه به اینکه  ، بنابراین یک خطا در بخش اطلاعاتی وجود دارد.

مرحله 6:                                                               x'= (10, 10, 2, 1) and M= (16, 17, 5, 3)

     10

       

      

با توجه به اینکه ، بنابراین یک خطا در بخش افزونه وجود دارد؛ به‌طوری‌که  با مقدار  جایگزین می‌شود و بدین ترتیب x'= (0, 1, 10, 10). شکل ۳، الگوریتم تشخیص و تصحیح یک خطا را نشان می‌دهد.

 

شکل 3: الگوریتم تشخیص خطا و تصحیح یک خطا

 

4-       الگوریتم‌های حسابی DNA پیشنهادی بر اساس مدل ادلمن-لیپتون با تشخیص دو خطا و تصحیح یک خطا

همان‌طور که قبلاً گفته شد، یکی از ویژگی‌های سیستم اعداد مانده‌ای،  عدم انتشار رقم نقلی است که عملیات محاسبات مولکولی را ساده می‌کند و از موازی‌سازی در محاسبات مولکولی و کارایی آن به طور مؤثر استفاده می‌کند. همچنین با توجه ‌به خاصیت تشخیص و تصحیح خطا در سیستم اعداد مانده‌ای، در اینجا از آن برای تشخیص دو خطا و تصحیح یک خطا در محاسبات مولکولی استفاده شده است. در این بخش الگوریتم‌های پیشنهادی برای انجام عملیات ریاضی DNA با تشخیص و تصحیح خطا بر اساس سیستم اعداد مانده‌ای افزونه، برای مدل ادلمن- لیپتون ارائه و پیاده‌سازی شده‌ است. در بخش اول یک الگوریتم عملیات ریاضی به نام جمع دو عدد مانده‌ای در سیستم DNA ارائه می‌شود و در بخش دوم الگوریتم‌های جدید، برای تحقق توابع مورد نیاز برای پیاده سازی حساب DNA با اعداد مانده‌ای ارائه شده است.  برای تحقق توابع موردنظر، برای پیاده‌سازی محاسبات مولکولی با سیستم اعداد مانده‌ای افزونه پیاده‌سازی مدل ادلمن – لیپتون به زبان سی پلاس پلاس در محیط ویژوال استودیو انجام شده است. 

جمع ریاضی دو عدد در سیستم اعداد مانده‌ای  1)          

در این روش ابتدا دو عدد باینری عادی که در تیوب های  و  قرار دارند توسط توابع Forward به اعدادی در مجموعه سیستم اعداد مانده‌ای تبدیل می‌شوند که اعداد مانده‌ای عدد اول در تیوب های  تا  و اعداد مانده‌ای عدد دوم در تیوب های  تا  قرار می‌گیرند. سپس عملیات جمع اعداد مانده‌ای، با توجه به پیمانه های   روی آنها انجام می‌شود. در ادامه نتیجه عمل جمع توسط تابع تشخیص و تصحیح خطا بررسی می‌شود. این روش در الگوریتم 1 نشان داده شده است. عملیات حسابی می‌تواند هر عملیاتی باشد که هدف در اینجا تشخیص و تصحیح خطاها می‌باشد.

2) توابع جدید در مدل ادلمن – لیپتون

در این بخش توابع جدید برای عملیات جمع و تشخیص و تصحیح خطا در محاسبات مولکولی بر اساس سیستم اعداد مانده‌ای افزونه در مدل ادلمن – لیپتون که در قسمت قبل معرفی شد، تعریف و پیاده‌سازی شده‌اند.

 

تابع جمع و تفریق پیمانه‌ای در مدل ادلمن – لیپتون

عملیات جمع و تفریق دو عمل اصلی در محاسبات سیستم اعداد مانده‌ای هستند. این عملیات نه‌تنها در محاسبات ریاضی سیستم اعداد مانده‌ای موردنیاز هستند؛ بلکه در مبدل مستقیم و معکوس هم موردنیاز هستند. تابع عملیات جمع پیمانه‌ای، در الگوریتم 2 برای پیمانه‌های  و نشان داده شده است. در این توابع ورودی اعداد مانده‌ای هستند و در  , به عنوان ورودی تابع تعریف شده‌اند. همچنین ورودی n به عنوان طول اعداد تعریف شده است و حاصل عملیات جمع در خروجی  ذخیره می‌شود. تابع Add_mod2np1 برای جمع مانده‌ای با توجه به پیمانه  ، تابع Add_mod2nm1 برای جمع مانده‌ای با توجه به پیمانه ، تابع Add_mod2np1 برای جمع مانده‌ای، با توجه به پیمانه  با 2n بیت و تابع Add_mod2n برای جمع مانده‌ای با توجه به پیمانه  انجام می‌شود و برای عملیات تفریق پیمانه‌ای اگر حاصل تفریق دو عدد مانده‌ای بزرگ‌تر از صفر باشد، پس جواب مساوی X-Y خواهد بود؛ یعنی حاصل تفریق کمتر از مقدار پیمانه m باشد (البته با فرض اینکه که ورودی‌ها هر کدام کمتر از پیمانه یعنی m هستند)؛ ولی اگر حاصل تفریق دو عدد مانده‌ای منفی باشد، یعنی رقم نقلی یک شود فقط کافی است که پیمانه یک‌بار با حاصل تفریق جمع شود تا حاصل درست به‌دست آید ]19[. این تابع در الگوریتم 3 نشان‌ داده‌ شده است. برای انجام عملیات جمع و تفریق پیمانه‌ای نیاز به توابع عملیات جمع و تفریق معمولی و باقی‌مانده پیمانه‌ای هست. بنابراین توابع calculate_remain_mod2nm1 (الگوریتم 4) و calculate_remain_mod2np1 (الگوریتم 5) برای پیدا کردن باقی‌مانده بر اساس پیمانه‌های  و j به ترتیب استفاده می‌شود.

 

 

 

 

 

 

 

 

 

 

تابع جمع و تفریق دو عدد با رقم نقلی و بدون رقم نقلی در مدل ادلمن – لیپتون

این تابع دو عدد n بیتی دریافت می‌کند که توسط دو رشته DNA مختلف در لوله آزمایش Tx، Ty  قرار دارند و نتیجه عملیات جمع در لوله آزمایش  Tout ذخیره و سرریز در Toverflow ارائه می‌شود. عملیات جمع یا با بیت نقلی یا بدون بیت نقلی انجام می‌شود. این تابع در الگوریتم 6 نشان داده شده است. برای تفریق، متمم دو، عدد دوم با عدد اول مشابه الگوریتم جمع انجام می‌شود که در الگوریتم 7 نشان داده شده است.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

تابع مبدل مستقیم در مدل ادلمن – لیپتون

فرایند تبدیل اعداد از سیستم وزنی به سیستم مانده‌ای توسط مبدل مستقیم انجام می‌گیرد. عدد X وارد مبدل دودویی به مانده‌ای شده و محاسبه باقی‌مانده در هر پیمانه به‌صورت جداگانه انجام می‌شود. با توجه ‌به مجموعه پیمانه  در این الگوریتم عدد باینری جهت تبدیل در  قرار دارد که به عنوان ورودی داده می شود و همچنین پیمانه‌های مورد نظر به عنوان ورودی در Tm به تابع داده می‌شوند و Tx  ها خروجی تابع می‌باشد که اعداد مانده‌ای تبدیل شده را برمی‌گرداند. این تابع در الگوریتم 8 تعریف و پیاده سازی شده است.

 

 

 

 

شکل 4:  مبدل مستقیم

محدوده دینامیکی در این مجموعه پیمانه برابر است با:

مرحله 2:
مرحله 3:	,

(7)	M=2n-1 × 2n+1 × 22n × 22n+1 = 24n-1

که یک عدد 4n بیتی است يعنی:

به عنوان مثال برای محدوده 4n بیتی داریم:

 با توجه ‌به اینکه =  است، x4 به صورت زیر به دست می آید]19[:

(8)

از طرفی، با توجه ‌به اینکه =  است، x2 به صورت زیر به دست می‌آید]19[:

(9)

با توجه ‌به اینکه   و  است، x1 به صورت زیر به دست می‌آید]19[:

(10)

(11)

در نهایت، با توجه ‌به اینکه   است، x3 به صورت زیر به دست می‌آید ]19[:   تابع مبدل معکوس در مدل ادلمن – لیپتون این تابع دو عدد مانده‌ای را دریافت کرده و عدد صحیح را برمی‌گرداند. الگوریتم این تابع در الگوریتم‌های 9 و 10 نشان‌ داده‌ شده است. فرض کنید مجموعه مدول 4 تایی  با مجموعه باقی‌مانده‌ای  را داریم. عدد وزنی  با توجه به دو پیمانه اطلاعاتی اول به صورت زیر محاسبه می‌شود: (12)   معکوس ضربی از  به پیمانه  برابر با  می‌باشد. (13)   (14)   قانون ۱: باقی‌مانده یک عدد مانده‌ای (v-) به پیمانه  برابر است با مکمل یک عدد v  یعنی  ]24[.  قانون 2: ضرب یک باقی‌مانده v در به پیمانه   برابر است با p  بیت چرخشی به چپ عدد v  یعنی ]24[. با توجه‌ به مجموعه پیمانه   و با توجه به باقی‌مانده‌های متناظر با عدد X به صورت  ، نمایش بیتی آنها به صورت زیر می‌باشد: (15)   اکنون، معادله (15) می‌تواند به‌صورت زیر ساده شود ]25[: (15)   (16)   (17)   (18)   (19)   معکوس ضربی از  به پیمانه  برابر با  می‌باشد. (20)   (21)   (22)   (23)   (24)   (25)   (26)   به طور مشابه، عدد وزنی  با توجه ‌به دو پیمانه افزونه آخر به‌ صورت زیر محاسبه می‌شود: (27)   معکوس ضربی از  به پیمانه  برابر با  می‌باشد، از این رو: (28)   (29)   بنابراین (28) به‌صورت زیر می‌شود: (30)   اکنون، برخی از ساده‌سازی‌های سطح بیت را در (31) اعمال می‌کنیم تا یک پیاده‌سازی کارآمد با DNA داشته باشیم. اول، می‌دانیم که   برابر است با p بیت عمل جمع A و B با نادیده گرفتن بیت نقلی A]].  از این رو: (31)   این واضح است که   ، بنابراین:  (32)   (33)         (34)     = این نکته قابل ‌ذکر است که معادله (33) با 2n بیت از  و معکوس  با در نظر نگرفتن بیت آخر و در نظر گرفتن بیت نقلی با مقدار یک، انجام می‌شود. اکنون، محاسبه نهایی از (32) را می‌توان به صورت زیر ساده کرد: از آنجایی که [1] 1 Residue Number System [2] 2 Redundant RNS [3] 3 Sticker [4] 1 Adleman-Lipton [5] 1 forward conversion [6] 2 Reverse conversion [7] 1 checking consistency [8] 2 Base-Extension      (35)