컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0574 |
|---|---|
| 분류(Section) | Contributed Talk |
| 분과(Session) | Combinatorics / Graph Theory / Cryptography / Coding Theory (SS-05) |
| 영문제목 (Title(Eng.)) |
On balanced sparse generator matrices for MDS codes |
| 저자(Author(s)) |
Son Hoang Dau1, Wentu Song1, Zheng Dong1, Chau Yuen1 Singapore University of Technology and Design1 |
| 초록본문(Abstract) | We show that given $n$ and $k$, for $q$ sufficiently large, there always exists an $[n,k]_q$ MDS code that has a generator matrix $G$ satisfying the following two conditions: (C1) Sparse: each row of $G$ has Hamming weight $n - k + 1$; (C2) Balanced: Hamming weights of the columns of $G$ differ from each other by at most one. Apart from being of theoretical interest, our study on balanced sparse generator matrices for MDS codes was motivated by its application in error correction for sensor networks. Supose $n$ sensors, $S_1$,...,$S_n$, collectively measure $k$ conditions $x_1$,...,$x_k$, such as temperature, pressure, light intensity, etc. Let $x = (x_1,...,x_k)$, where $x_i \in F_q$ (i = 1,...,k), and $F_q$ is a finite field of $q$ elements. These sensors transmit the information they collected to a base station. Furthermore, each sensor performs some encoding on the information it has, before transmitting the information back to the base station in the following way. Let $G$ be an $k \times n$ generator matrix of an $[n,k,d]_q$ error-correcting code. Sensor $S_i$ transmits the scalar product of $x$ and column $i$ of $G$ to the base station. It is well known in classical coding theory that this scheme allows the base station to retrieve $x$ when at most $[(d-1)/2]$ sensors transmit wrong information. If $G$ is sparse then in average, each sensor only needs to measure a few among $k$ conditions in order to do the aforementioned encoding. On top of that, if columns of $G$ has approximately the same number of nonzero entries then the sensors are required to measure approximately the same number of conditions. This balance guarantees an even distribution of workload among sensors, which is an important criterion for sensor networks where energy saving is a critical issue. |
| 분류기호 (MSC number(s)) |
94B05 |
| 키워드(Keyword(s)) | MDS codes, sparse, balanced, error correction, sensor network |
| 강연 형태 (Language of Session (Talk)) |
English |