Coding Theory: Consecutive Switch Codes

שרית בוזגלו (אונ' קליפורניה(
יום ראשון, 3.7.2016, 14:30
טאוב 601

Switch codes are a coding scheme which enables one to encode the input packets into the banks such that the packet requests by the output ports can be answered efficiently. Mathematically speaking, a switch code is required to satisfy the following property. Assume that there are n​ input ports, k​ output ports, and m​ banks. In each generation the n​ packets from the input ports are encoded into m​ packets which are stored in the banks. Then, every request from the output ports for k​ packets, which may come from previous generations, has to be answered by reading at most one packet from each bank.

In this work we present a construction of binary switch codes that improves upon the best binary switch codes for the case n=k​. We also study a new type of switch codes that can simultaneously deliver large symbol requests and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. In an ℓ​-consecutive request of k​ packets, the k​ packets are required to belong to ℓ​-consecutive generations. For this new request model we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. We present several code constructions and prove the optimality of our construction of combinatorial 2-consecutive switch codes.

Joint work with Eitan Yaakobi, Yuval Cassuto, and Paul H. Siegel.

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