{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T14:21:55Z","timestamp":1767968515754,"version":"3.49.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,2,24]],"date-time":"2015-02-24T00:00:00Z","timestamp":1424736000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MK-5407.2013.9 of the president of Russia"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2015,2,24]]},"abstract":"<jats:p>Fast algorithms are proposed for encoding and reconstructing data in RAID based on Reed-Solomon codes. The proposed approach is based on the cyclotomic fast Fourier transform algorithm and enables one to significantly reduce the number of expensive Galois field multiplications required. The complexity of the obtained algorithms is much lower than those for existing MDS array codes. Software implementation of the proposed algorithms is discussed. The performance results show that the new algorithms provide substantially better performance compared with the standard algorithm.<\/jats:p>","DOI":"10.1145\/2700308","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T14:08:19Z","timestamp":1425391699000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Low-Complexity Implementation of RAID Based on Reed-Solomon Codes"],"prefix":"10.1145","volume":"11","author":[{"given":"P.","family":"Trifonov","sequence":"first","affiliation":[{"name":"Saint-Petersburg State Polytechnic University, Saint-Petersburg, Russia"}]}],"member":"320","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Symposium on Communications and Information Technologies (ISCIT\u201907)","author":"Al Ghouwayel A.","unstructured":"A. Al Ghouwayel , Y. Louet , A. Nafkha , and J. Palicot . 2007. On the FPGA implementation of the Fourier transform over finite fields GF(2m) . In Proceedings of the International Symposium on Communications and Information Technologies (ISCIT\u201907) . 146--151. A. Al Ghouwayel, Y. Louet, A. Nafkha, and J. Palicot. 2007. On the FPGA implementation of the Fourier transform over finite fields GF(2m). In Proceedings of the International Symposium on Communications and Information Technologies (ISCIT\u201907). 146--151."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2011.060911.090145"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777458"},{"key":"e_1_2_1_4_1","volume-title":"Theory and Practice of Error Control Codes","author":"Blahut R.","unstructured":"R. Blahut . 1984. Theory and Practice of Error Control Codes . Addison-Wesley . R. Blahut. 1984. Theory and Practice of Error Control Codes. Addison-Wesley."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.364531"},{"key":"e_1_2_1_6_1","unstructured":"J. Blomer M. Kalfanej R. Karp M. Karpinski M. Luby and D. Zuckerman. 1995. An XOR-Based Erasure-Resilient Coding Scheme. Tech. Rep. International Computer Science Institute Berkeley California.  J. Blomer M. Kalfanej R. Karp M. Karpinski M. Luby and D. Zuckerman. 1995. An XOR-Based Erasure-Resilient Coding Scheme. Tech. Rep. International Computer Science Institute Berkeley California."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2008.2009891"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2009.2014292"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"E. Chu and A. George. 2000. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. CRC Press.  E. Chu and A. George. 2000. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. CRC Press.","DOI":"10.1201\/9781420049961"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 3rd USENIX Conference on File and Storage Technologies. USENIX Association","author":"Corbett P.","unstructured":"P. Corbett , B. English , A. Goel , T. Grcanac , S. Kleiman , J. Leong , and S. Sankar . 2004. Row-diagonal parity for double disk failure correction . In Proceedings of the 3rd USENIX Conference on File and Storage Technologies. USENIX Association , Berkeley, CA, 1--14. P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, and S. Sankar. 2004. Row-diagonal parity for double disk failure correction. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies. USENIX Association, Berkeley, CA, 1--14."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.982"},{"key":"e_1_2_1_12_1","unstructured":"F. Didier. 2009. Efficient erasure decoding of reed-solomon codes. arXiv:1301.5536v1.  F. Didier. 2009. Efficient erasure decoding of reed-solomon codes. arXiv:1301.5536v1."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0032946006020074"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2011.6033725"},{"key":"e_1_2_1_15_1","article-title":"A novel method for computation of the discrete Fourier transform over characteristic two finite field of even extension degree","author":"Fedorenko S. V.","year":"2011","unstructured":"S. V. Fedorenko . 2011 b. A novel method for computation of the discrete Fourier transform over characteristic two finite field of even extension degree . IEEE Transactions on Information Theory. Available at http:\/\/arxiv.org\/abs\/1112.1639. S. V. Fedorenko. 2011b. A novel method for computation of the discrete Fourier transform over characteristic two finite field of even extension degree. IEEE Transactions on Information Theory. Available at http:\/\/arxiv.org\/abs\/1112.1639.","journal-title":"IEEE Transactions on Information Theory. Available at http:\/\/arxiv.org\/abs\/1112.1639."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025119.1025641"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of 6th IEEE International Symposium on Network Computing and Applications. 79--86","author":"Huang C.","unstructured":"C. Huang , M. Chen , and J. Li . 2007. Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems . In Proceedings of 6th IEEE International Symposium on Network Computing and Applications. 79--86 . C. Huang, M. Chen, and J. Li. 2007. Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems. In Proceedings of 6th IEEE International Symposium on Network Computing and Applications. 79--86."},{"key":"e_1_2_1_18_1","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","unstructured":"D. E. Knuth . 1973. The Art of Computer Programming . Vol. 2 . Addison-Wesley . D. E. Knuth. 1973. The Art of Computer Programming. Vol. 2. Addison-Wesley."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"R. Lidl and H. Niederreiter. 1996. Finite Fields. Cambridge University Press.  R. Lidl and H. Niederreiter. 1996. Finite Fields. Cambridge University Press.","DOI":"10.1017\/CBO9780511525926"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2007.910595"},{"key":"e_1_2_1_21_1","volume-title":"The Theory of Error-Correcting Codes","author":"MacWilliams F. J.","unstructured":"F. J. MacWilliams and N. J. A. Sloane . 1977. The Theory of Error-Correcting Codes . North-Holland Publishing Company . F. J. MacWilliams and N. J. A. Sloane. 1977. The Theory of Error-Correcting Codes. North-Holland Publishing Company."},{"key":"e_1_2_1_22_1","volume-title":"Error Correction Coding. Mathematical Methods and Algorithms","author":"Moon T. K.","unstructured":"T. K. Moon . 2005. Error Correction Coding. Mathematical Methods and Algorithms . Wiley . T. K. Moon. 2005. Error Correction Coding. Mathematical Methods and Algorithms. Wiley."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199709)27:9%3C995::AID-SPE111%3E3.3.CO;2-Y"},{"key":"e_1_2_1_26_1","volume-title":"Jerasure: A Library in C Facilitating Erasure Coding for Storage Applications -- version 2.0. Tech. Rep. UT-EECS-14-721","author":"Plank J. S.","year":"2014","unstructured":"J. S. Plank and K. M. Greenan . 2014 . Jerasure: A Library in C Facilitating Erasure Coding for Storage Applications -- version 2.0. Tech. Rep. UT-EECS-14-721 , University of Tennessee . J. S. Plank and K. M. Greenan. 2014. Jerasure: A Library in C Facilitating Erasure Coding for Storage Applications -- version 2.0. Tech. Rep. UT-EECS-14-721, University of Tennessee."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of 11th Usenix Conference on File and Storage Technologies.","author":"Plank J. S.","unstructured":"J. S. Plank , K. M. Greenan , and E. L. Miller . 2013. Screaming fast Galois field arithmetic using intel SIMD instructions . In Proceedings of 11th Usenix Conference on File and Storage Technologies. J. S. Plank, K. M. Greenan, and E. L. Miller. 2013. Screaming fast Galois field arithmetic using intel SIMD instructions. In Proceedings of 11th Usenix Conference on File and Storage Technologies."},{"key":"e_1_2_1_28_1","volume-title":"7th IEEE Consumer Communications and Networking Conference.","author":"Soro A.","unstructured":"A. Soro and J. Lacan . 2010. FNT-based Reed-Solomon erasure codes . In 7th IEEE Consumer Communications and Networking Conference. A. Soro and J. Lacan. 2010. FNT-based Reed-Solomon erasure codes. In 7th IEEE Consumer Communications and Networking Conference."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of IEEE International Symposium on Information Theory. 1240--1244","author":"Tamo I.","unstructured":"I. Tamo , Z. Wang , and J. Bruck . 2011. MDS array codes with optimal rebuilding . In Proceedings of IEEE International Symposium on Information Theory. 1240--1244 . I. Tamo, Z. Wang, and J. Bruck. 2011. MDS array codes with optimal rebuilding. In Proceedings of IEEE International Symposium on Information Theory. 1240--1244."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 11th International Symposium on Problems of Redundancy in Information and Control Systems.","author":"Trifonov P.","year":"2007","unstructured":"P. Trifonov . 2007 . Matrix-vector multiplication via erasure decoding . In Proceedings of the 11th International Symposium on Problems of Redundancy in Information and Control Systems. P. Trifonov. 2007. Matrix-vector multiplication via erasure decoding. In Proceedings of the 11th International Symposium on Problems of Redundancy in Information and Control Systems."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2012.6404732"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026171930630"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2011.2106778"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2011.2178844"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS\u201911)","author":"Wu X.","unstructured":"X. Wu and Z. Yan . 2011. Computational complexity of cyclotomic fast Fourier transforms over characteristic-2 fields . In Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS\u201911) . 1--6. X. Wu and Z. Yan. 2011. Computational complexity of cyclotomic fast Fourier transforms over characteristic-2 fields. In Proceedings of the IEEE Workshop on Signal Processing Systems (SiPS\u201911). 1--6."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.746809"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700308","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:44Z","timestamp":1750223264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,24]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,2,24]]}},"alternative-id":["10.1145\/2700308"],"URL":"https:\/\/doi.org\/10.1145\/2700308","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,24]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}