Coding Theory: Nearly Optimal Robust Positioning Sequences

וואי הנג'יה (אונ' בן-גוריון)
יום ראשון, 26.5.2019, 14:30
טאוב 601

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this talk, we focus on the 1-dimensional case, i.e., robust positioning sequences (RPS). We present constructions of RPSs along with efficient locating algorithms. In particular, we construct a class of q-ary RPSs which are robust to a constant fraction of errors and have asymptotically optimal rate. We also obtain a class of binary RPSs which are robust to a constant number of errors, and the redundancy of the proposed sequences differs from the lower bound only by a small term.

בחזרה לאינדקס האירועים