Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the failing cases of the Johnson bound for error-correcting codes. | On the failing cases of the Johnson bound for error-correcting codes Wolfgang Haas Albert-Ludwigs-Universitat Mathematisches Institut Eckerstr. 1 79104 Freiburg Germany wolfgang_haas@gmx.net Submitted Mar 4 2008 Accepted Apr 4 2008 Published Apr 18 2008 Mathematics Subject Classification 94B25 94B65 Abstract A central problem in coding theory is to determine Aq n 2e 1 the maximal cardinality of a q-ary code of length n correcting up to e errors. When e is fixed and n is large the best upper bound for A n 2e 1 the binary case is the well-known Johnson bound from 1962. This however simply reduces to the sphere-packing bound if a Steiner system S e 1 2e 1 n exists. Despite the fact that no such system is known whenever e 5 they possibly exist for a set of values for n with positive density. Therefore in these cases no non-trivial numerical upper bounds for A n 2e 1 are known. In this paper the author presents a technique for upper-bounding Aq n 2e 1 which closes this gap in coding theory. The author extends his earlier work on the system of linear inequalities satisfied by the number of elements of certain codes lying in k-dimensional subspaces of the Hamming Space. The method suffices to give the first proof that the difference between the sphere-packing bound and Aq n 2e 1 approaches infinity with increasing n whenever q and e 2 are fixed. A similar result holds for Kq n R the minimal cardinality of a q-ary code of length n and covering radius R. Moreover the author presents a new bound for A n 3 giving for instance A 19 3 26168. 1 Introduction In the whole paper let q denote an integer greater than one and Q a set with IQ I q. The Hamming distance d A p between A x1 . xn 2 Qn and p y-1 . yn 2 Qn is defined by d A p i 2 1 . ng xi yig . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R55 1 Let Bq A e denote the Hamming sphere with radius e centered on A 2 Qn Bq A e p 2 Qn d p A eg. We set Vq n e Bq A e X q- ứ 0 i e A and Vq n e p 2 Qn d p A eg for any A 2 Qn. Assume
