Giảm độ phức tạp thuật toán tìm phác đồ sửa lỗi xóa của mã Reed-Solomon RS (n, k), n - k = 2
Article Sidebar
Main Article Content
Giảm độ phức tạp thuật toán tìm phác đồ sửa lỗi xóa của mã Reed-Solomon RS (n, k), n - k = 2
Tóm tắt
Các mã Reed-Solomon RS(n, k) là các mã được sử dụng phổ biến nhất hiện nay trong các hệ thống lưu trữ dữ liệu phân tán nhưng chúng có nhược điểm lớn bởi tiêu tốn lượng băng thông khổng lồ khi sửa các lỗi xóa của hệ thống. Phương pháp sửa lỗi xóa cho mã Reed-Solomon bằng cách áp dụng hàm vết do Guruswami và Wootters (Guruswami and Wootters, 2017) đề xuất làm giảm đáng kể băng thông sửa lỗi. Tuy nhiên việc xác định các phác đồ sửa lỗi cho một hoặc nhiều lỗi xóa theo phương pháp này vẫn có độ phức tạp rất lớn ngay cả trên các trường mã hóa nhỏ như F16 , F64 hay F256 . Vì vậy các phương pháp làm giảm độ phức tạp của thuật toán tìm phác đồ sửa lỗi cho mã Reed-Solomon là một vấn đề đáng lưu tâm. Bài báo của chúng tôi đưa ra một số kết quả về giảm độ phức tạp thuật toán tìm phác đồ sửa lỗi xóa cho mã Reed-Solomon, đặc biệt là cho các mã có phần dư n - k = 2.
Article Details
Tác phẩm này được cấp phép theo Giấy phép quốc tế Creative Commons Attribution-NonCommercial-NoDeri Phái sinh 4.0 .
Tài liệu tham khảo
- Berman, A. & et al. (2021), "Repairing Reed-Solomon Codes Evaluated on Subspaces," 2021 IEEE Int. Symp. Inf. Theory, 2021.
- Dau, H., & Milenkovic, O. (2017). Optimal Repair Schemes for Some Families of Full-Length ReedSolomon Codes. Proc. IEEE Int. Symp. Inf. Theory, 346–350.
- Dau, H. & et al. (2018). Repairing Reed-Solomon Codes With Multiple Erasures. IEEE Trans. Inf. Theory, 64(10), 6567–6582, doi: 10.1109/TIT.2018.2827942.
- Dau, H., & et al. (2021). Repairing Reed-Solomon codes via subspace polynomials. IEEE Trans. Inf. Theory, 67(10), 6395–6407, 2021, doi: 10.1109/TIT.2021.3071878.
- Dimakis, A. G. & et al (2010). Network coding for distributed storage systems. IEEE transactions on information theory, 56(9):4539–4551.
- Guruswami, V., & Wootters, M. (2017). Repairing Reed-Solomon Codes. IEEE Trans. Inf. Theory, 63(9), 5684–5698.
- Li, W. Q., & et al. (2017). A Tradeoff between the Sub-Packetization Size and the Repair Bandwidth for Reed-Solomon Code. 55th annual allerton conference on communication, control, and computing (Allerton), 942–949.
- Mardia, J., & et al. (2019). Repairing Multiple Failures for Scalar MDS Codes. IEEE Trans. Inf. Theory, 65(5), 2661–2672, doi: 10.1109/TIT.2018.2876542.
- MacWilliams, F. J., & Sloane, N. J. A. (1977). The theory of error-correcting code. Published by: NorthHolland Publishing Company Amsterdam · New York · Oxford.
- Li, H., & et al. (2019). On the Sub-Packetization Size and the Repair Bandwidth of Reed-Solomon Codes. IEEE Trans. Inf. Theory, 65(9), 5484–5502.[1] A. Berman, S. Buzaglo, A. Dor, Y. Shany, and I. Tamo, "Repairing Reed-Solomon Codes Evaluated on Subspaces," 2021 IEEE Int. Symp. Inf. Theory, 2021.
- Sathiamoorthy, M., & et al. (2013). XORing elephants: Novel erasure codes for big data. Proc. VLDB Endow., 6(5), 325–336, doi: 10.14778/2535573.2488339.
- Shanmugam, K. & et al. (2014). A repair framework for scalar MDS codes. IEEE Journal on Selected Areas in Communications, 32(5):998–1007.
- Zhang, Y., & et al. (2019). An Improved Cooperative Repair Scheme for Reed-Solomon Codes. Proc. - 2019 19th Int. Symp. Commun. Inf. Technol. Isc. 2019, 525–530, doi: 10.1109/ISCIT.2019.8905159.