The Journal of Korean Institute of Communications and Information Sciences (한국통신학회논문지)

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지
DOI QR코드

DOI QR Code

Construction of [2k-1+k, k, 2k-1+1] Codes Attaining Griesmer Bound and Its Locality

Griesmer 한계식을 만족하는 [2k-1+k, k, 2k-1+1] 부호 설계 및 부분접속수 분석

  • Kim, Jung-Hyun (School of Electrical and Electronic Engineering, Yonsei University) ;
  • Nam, Mi-Young (School of Electrical and Electronic Engineering, Yonsei University) ;
  • Park, Ki-Hyeon (School of Electrical and Electronic Engineering, Yonsei University) ;
  • Song, Hong-Yeop (School of Electrical and Electronic Engineering, Yonsei University)
  • Received : 2014.12.17
  • Accepted : 2015.02.16
  • Published : 2015.03.31
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we introduce two classes of optimal codes, [$2^k-1$, k, $2^{k-1}$] simplex codes and [$2^k-1+k$, k, $2^{k-1}+1$] codes, attaining Griesmer bound with equality. We further present and compare the locality of them. The [$2^k-1+k$, k, $2^{k-1}+1$] codes have good locality property as well as optimal code length with given code dimension and minimum distance. Therefore, we expect that [$2^k-1+k$, k, $2^{k-1}+1$] codes can be applied to various distributed storage systems.

본 논문에서는 Griesmer 한계식을 만족하는 [$2^k-1$, k, $2^{k-1}$] 심플렉스(simplex) 부호와 [$2^k-1+k$, k, $2^{k-1}+1$] 부호를 소개한다. 또한 두 부호의 부분접속수(locality)에 대해 유도하고 그 값들을 비교한다. [$2^k-1+k$, k, $2^{k-1}+1$] 부호는 주어진 부호차원과 최소거리에 대해 최적의 부호길이를 가질 뿐만 아니라 좋은 부분접속수 특성을 가진다. 그러므로 이 부호는 다양한 분산 저장 시스템에 널리 사용될 수 있을 것으로 기대된다.

Keywords

References

  1. J.-C. Park, "Improving data availability by data partitioning and partial overlapping on multiple cloud storages," J. KICS, vol. 36, no. 12, Nov. 2011.
  2. T.-H. Kim, J. Kim, and Y. I. Eom, "A scheme on high-performance caching and high-capacity file transmission for cloud storage optimization," J. KICS, vol. 37C, no. 8, Aug. 2012.
  3. J.-H. Kim, J. S. Park, K.-H. Park, M. Y. Nam, and H.-Y. Song, "Trends of regenerating codes for next-generation cloud storage systems," Inf. Commun. Mag., vol. 31, no. 2, pp. 125-131, Feb. 2014.
  4. J.-H. Kim and H.-Y. Song, "Coding techniques for distributed storage systems," in Proc. 2013 CITS 3rd CITW, Samsung Electronics, Seoul, Korea, Oct. 2013.
  5. J. S. Park, J.-H. Kim, K.-H. Park, and H.-Y. Song, "Average repair read cost of linear repairable code ensembles," J. KICS, vol. 39B, no. 11, Nov. 2014.
  6. P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, "On the locality of codeword symbols," IEEE Trans. Inform. Theory, vol. 58, no. 11, pp. 6925-6934, Nov. 2012. https://doi.org/10.1109/TIT.2012.2208937
  7. D. S. Papailiopoulos and A. G. Dimakis, "Locally repairable codes," IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 5843-5855, Oct. 2014. https://doi.org/10.1109/TIT.2014.2325570
  8. V. Cadambe and A. Mazumdar, "An upper bound on the size of locally recoverable codes," in Proc. IEEE Int. Symp. Netw. Coding, pp. 1-5, Calgary, Canada, Jun. 2013.
  9. C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin, "Erasure coding in Windows Azure Storage," in Proc. 2012 USENIX Annu. Technical Conf., pp. 1-12, Boston, USA, Jun. 2012.
  10. M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur, "XORing Elephants: novel erasure codes for Big Data," in Proc. 39th Int. Conf. Very Large Data Bases, vol. 6, no. 5, pp. 325-336, Trento, Italy, Aug. 2013.
  11. M. Kuijper and D. Napp, Erasure codes with simplex locality(2014), Last access(Feb. 16, 2015), http://arxiv.org/abs/1403.2779.
  12. J. H. Griesmer, "A bound for error-correcting codes," IBM J. Res. Develop., vol. 4, pp. 532-542, Nov. 1960. https://doi.org/10.1147/rd.45.0532
  13. W. C. Huffman and V. Pless, Fundamentals of error correcting codes, Cambridge, 2003.
  14. J.-H. Kim and H.-Y. Song, "Simple construction of [$2^k-1+k,\;k,\;2^{k-1}+1$] code attaining the Griesmer bound," in Proc. 9th Joint Conf. Commun. & Inf., pp. 420-422, Icheon, Korea, Apr. 1999.
  15. T. Helleseth, "New constructions of codes meeting the Griesmer bound," IEEE Trans. Inf. Theory, vol. 29, no. 3, pp. 434-439, Mar. 1983. https://doi.org/10.1109/TIT.1983.1056658
  16. M. N. Krishnan, N. Prakash, V. Lalitha, B. Sasidharan, P. V. Kumar, S. Narayanamurthy, R. Kumar, and S. Nandi, "Evaluation of codes with inherent double replication for Hadoop," in Proc. 6th USENIX Workshop on Hot Topics in Storage and File Systems, pp. 1-5, Philadelphia, USA, Jun. 2014.
  17. M. Shahabinejad, M. Khabbazian, and M. Ardakani, "An efficient binary locally repairable code for Hadoop distributed file system," IEEE Commun. Lett., vol. 18, no. 8, pp. 1287-1290, Aug. 2014. https://doi.org/10.1109/LCOMM.2014.2332491
  18. F. J. MacWilliams and N. J. A. Sloane, The theory of error correcting codes, North-Holland Mathematical Library, 1977.

Cited by

  1. 두 개의 다른 부분접속수 요건을 가진 부분접속 복구 부호 vol.41, pp.12, 2016, https://doi.org/10.7840/kics.2016.41.12.1671