Паралельне сортування на основі аналогової нейронної схеми знаходження найбільших за значеннями з множини сигналів

Authors: 
Тимощук П. В.

Національний університет “Львівська політехніка”, кафедра систем автоматизованого проектування

Для отримання розв’язку задачі паралельного сортування запропоновано використовувати аналогову нейронну схему знаходження найбільших за значеннями з множини сигналів. Схема є швидкісною, має просту структуру і може бути реалізована у сучасному апаратному забезпеченні. Роздільна здатність схеми є теоретично нескінчен- ною і не залежить від значення її параметра. Середній час, необхідний для збіжності траєкторії змінної стану схеми до встановленого режиму, не залежить від розмірності вхідних даних. Наведено результати комп’ютерного моделювання схеми, які підтвер- джують теоретичні положення. Отримані результати свідчать про доцільність викорис- тання схеми для паралельного сортування.

1. Wang J. Analysis and design of an analog sorting network // IEEE Trans. Neural Netw., vol. 6, no. 4, pp. 962–971, Jul. 1995. 2. Francis D.E. and Mathieson I.D. Benchmark parallel sort for shared memory multi-processors // IEEE Trans. Comput., vol. C-37, pp. 1619–1626, 1988. 3. Chakrabarti C. Sorting network based architectures for median filters // IEEE Trans. Circuits Syst. II, vol. 40, no. 11, pp. 723–727, Nov. 1993. 4. Chakrabarti C. and Wang L.-Y. Novel sorting network-based architecture for rank order filters // IEEE Trans. VLSI Syst., vol. 2, no. 4, pp. 502–507, Dec. 1994. 5. Johnson B. Design and Analysis of Fault Tolerant Digital Systems, Reading, MA: Addison-Wesley, 1989. 6. Rovetta S. and Zunino R. Minimal-connectivity programmable circuit for analog sorting // IEE Proc. Circuits, Devices Syst., vol. 146, no. 3, pp. 108–110, Aug. 1999. 7. Wang J. Analysis and design of a k-winners-take-all model with a single state variable and the Heaviside step activation function // IEEE Trans. on Neural Networks 9, 1496-1506 (2010). 8. Knuth D.E. The Art of Computer Programming, Sorting and Searching. Reading, MA: Addison-Wesley, 1973. 9. Ald S.G. Parallel Sorting Algorithms. Orlando, FL: Academic, 1985. 10. Alnuweiri H.M. and Kumar V. K. P. Optimal VLSI sorting with reduced number of processors // IEEE Trans. Comput., vol. C-40, pp. 105–110, 1991. 11. Brockett R.W. Dynamical systems that sort lists, diagonize matrices and solve linear programming problems. Linear Algebra and Its Applications, vol. 146, pp. 79–91, 1991. 12. Takefuji T. and Lee K.-C. A super parallel sorting algorithm based on neural networks // IEEE Trans. Circuit Syst., vol. CAS-37, no. 11, pp. 1425–1429, 1990. 13. Kwon T.M. and Zervakis M. A parallel sorting network without comparators: A neural network approach // in Proc. Int. Joint Conf. Neural Networks, vol. 1, Baltimore, MD, 1992, pp. 701–706. 14. Tseng Y.-H. and Wu J.-L. Solving sorting and related problems by quadratic perceptrons // Electron. Lett., vol. 28, no. 10, pp. 906– 908, 1992. 15. Тимощук П.В. Модель аналогової нейронної схеми ідентифікації найбільших сигналів // Вісн. Нац. ун-ту “Львівська політехніка” “Комп’ютерні системи та мережі”. – 2012. – № 745. – С. 180–185. 16. Kwon T.M. and Zervakls M. KWTA networks and their applications // Multidimensional Syst. Signal Process. – 1995. – Vol. 6, no. 4. – Р. 333–346.