检索结果-内蒙古大学图书馆

Nonlinear index coding Outperforming the Linear Optimum

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第8期55卷 3544-3551页

作者： Lubetzky, Eyal Stav, Uri Microsoft Res Theory Grp Redmond WA 98052 USA Tel Aviv Univ Raymond & Beverly Sackler Fac Exact Sci Sch Comp Sci IL-69978 Ramat Aviv Israel

The following source coding problem was introduced by Birk and Kol: a sender holds a word x is an element of {0, 1}(n), and wishes to broadcast a codeword to n receivers, R-1, ... , R-n. The receiver R-i is interested in x(i), and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n vertices, where i(j) is an edge iff R-i knows the bit x(j). An index code for G is an encoding scheme which enables each R-i to always reconstruct x(i), given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram, and Kol (FOCS'06). They introduced a graph parameter, minrk(2) (G), which completely characterizes the length of an optimal linear index code for G. They showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal. In this work, we disprove the main conjecture of Bar-Yossef, Birk, Jayram, and Kol in the following strong sense: for any epsilon > 0 and sufficiently large n, there is an n-vertex graph G so that every linear index code for G requires codewords of length at least n(1-epsilon), and yet a nonlinear index code for G has a word length of n(epsilon). This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson. In addition, we study optimal index codes in various, less restricted, natural models, and prove several related properties of the graph parameter minrk(G).

关键词： index coding linear and nonlinear source coding Ramsey constructions

来源：评论

学校读者我要写书评

暂无评论

Error Correction for index coding With Coded Side Information

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第6期63卷 3712-3728页

作者： Byrne, Eimear Calderini, Marco Univ Coll Dublin Sch Math & Stat Res Innovat & Impact Dublin Ireland Univ Trento Dept Math Trento Italy

index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. A well-known application is satellite communications, as described in one of the earliest papers on the subject (Birk and Kol, 1998). It is readily seen that if the sender has knowledge of its clients' requests and their side-information sets, then the number of packet transmissions required to satisfy all users' demands can be greatly reduced if the data are encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance I of the index coding with side-information (ICSI) problem. The encoding function is called the index code of I, and the number of transmissions, resulting from the encoding is referred to as its length. The main ICSI problem is to determine the optimal length of an index code and instance I. As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. These questions have been addressed by several authors (e.g., see Alon et al. 2008, Bar-Yossef et al. 2011, Blasiak et al. 2013), often taking a graph-theoretic approach. Two interesting generalizations of the problem that have appeared in the literature are the subject of this paper. The first of these is the case of index coding with coded side information (Dai et al. 2014), in which linear combinations of the source data are both requested by and held as users' side-information. This generalization has applications, for example, to relay channels and necessitates algebraic rather than combinatorial methods. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise (Dau et al. 2013). In this paper, we characterize the optimal length of a scalar or vector linear index code with coded side information (ICC

关键词： index coding min-rank error correction minimum distance network coding coded side information

来源：评论

学校读者我要写书评

暂无评论

Error Correction for index coding With Side Information

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第3期59卷 1517-1531页

作者： Dau, Son Hoang Skachek, Vitaly Chee, Yeow Meng Nanyang Technol Univ Div Math Sci Sch Phys & Math Sci Singapore 637371 Singapore

A problem of index coding with side information was first considered by Birk and Kol in 1998. In this study, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the alpha-bound and the kappa-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with a maximum distance separable classical code is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced. Several bounds on the length of static ECICs are derived, and constructions for static ECICs are discussed. Connections of th

关键词： Broadcast error correction index coding minimum distance network coding side information

来源：评论

学校读者我要写书评

暂无评论

Optimal Linear Broadcast Rates of Some Two-Sender Unicast index coding Problems

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第6期67卷 3965-3977页

作者： Arunachala, Chinmayananda Aggarwal, Vaneet Rajan, B. Sundar Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India Purdue Univ Sch IE W Lafayette IN 47907 USA

The two-sender unicast index coding problem consists of two senders, each having a different set of messages. Some messages may be common to both the senders. Each receiver demands a unique message and has a subset of messages known as its side-information. The senders transmit coded messages by availing the knowledge of the side-information of all the receivers, such that all the receivers are able to decode their demands. The aim is to find the optimal aggregate number of coded transmissions per message length (also called the optimal broadcast rate with finite length messages), and its limiting value as the message length tends to infinity (also called the optimal broadcast rate). In this paper, only linear coding schemes are considered. Optimal linear broadcast rate for any finite message length and optimal linear broadcast rate for a basic class of the two-sender unicast index coding problem are established. Optimal code-constructions are also provided. These results are given in terms of the corresponding results of three independent single-sender sub-problems of the two-sender unicast index coding problem. Proof techniques used to obtain the results for the two-sender problem are shown to be useful in obtaining the results for some classes of the multi-sender unicast index coding problem.

关键词： index coding side-information two-sender unicast index coding optimal linear broadcast rate

来源：评论

学校读者我要写书评

暂无评论

Multi-Sender index coding for Collaborative Broadcasting: A Rank-Minimization Approach

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第2期67卷 1452-1466页

作者： Li, Min Ong, Lawrence Johnson, Sarah J. Univ Newcastle Sch Elect Engn & Comp Callaghan NSW 2308 Australia Macquarie Univ Sch Engn Sydney NSW 2109 Australia

We consider a Multi-Sender Unicast index-coding (MSUIC) problem, where in a broadcast network, multiple senders collaboratively send distinct messages to multiple receivers, each having some subset of the messages a priori. The aim is to find the shortest index code that minimizes the total number of coded bits sent by the senders. In this paper, built on the classic single-sender minrank concept, we develop a new rank-minimization framework for MSUIC that explicitly takes into account the sender message constraints and minimizes the sum of the ranks of encoding matrices subject to the receiver decoding requirements. This framework provides a systematic way to construct multi-sender linear index codes and to study their capability in achieving the shortest index codelength per message length (i.e., the optimal broadcast rate). In particular, we establish the optimal broadcast rate for all critical MSUIC instances with up to four receivers and show that a binary linear index code is optimal for all, except 15 instances with four receivers. We also propose a heuristic algorithm (in lieu of exhaustive search) to solve the rank-minimization problem. The effectiveness of the algorithm is validated by numerical studies of MSUIC instances with four or more receivers.

关键词： Broadcast networks edge caching index coding message side information rank minimization

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Time Algorithm for Pliable index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第2期64卷 979-999页

作者： Song, Linqi Fragouli, Christina Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA

In pliable index coding, we consider a server with m messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most O(log(2)(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-time algorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by O(log(2)(n)) broadcast transmissions. We extend our algorithm to the t-requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most O(t log(n) + log(2)(n)) broadcast transmissions. We construct lower bound instances that require at least Omega(log(n)) transmissions for linear pliable index coding and at least Omega(t + log(n)) transmissions for the t-requests case, indicating that both our upper and lower bounds are polynomials of log(n) and differ within a factor of O(log(n)). We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely Theta(log(n)), as compared with the Theta(n/log(n)) for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.

关键词： Pliable index coding index coding t-requests polynomial time algorithm greedy algorithm random graphs

来源：评论

学校读者我要写书评

暂无评论

Critical Graphs in index coding

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2015年第2期33卷 225-235页

作者： Tahmasbi, Mehrdad Shahrasbi, Amirbehshad Gohari, Amin Sharif Univ Technol Dept Elect Engn Tehran *** Iran

In this paper, we define critical graphs as minimal graphs that support a given set of rates for the index coding problem and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic nonlinear index coding, each critical graph is a union of disjoint strongly connected subgraphs. On the other hand, we identify a non-USCS critical graph for a one-shot nonlinear index coding problem. Next, we identify a few graph structures that are critical. In addition, we show that the capacity region of the index coding is additive for union of disjoint graphs.

关键词： index coding critical graphs

来源：评论

学校读者我要写书评

暂无评论

Two reversible data hiding schemes for VQ-compressed images based on index coding

引用

IET IMAGE PROCESSING 2018年第7期12卷 1195-1203页

作者： Rahmani, Peyman Dastghaibyfard, Gholamhossein Shiraz Univ Dept Comp Sci & Engn Shiraz Iran

This study proposes two reversible data hiding (RDH) schemes for vector quantisation (VQ)-compressed images based on switching-tree coding (STC) and dynamic tree-coding scheme (DTCS). Most developed VQ-based RDH schemes produce non-legitimate codes as output. In order to preserve the legitimacy of the embedded VQ code, some schemes embed data into VQ indices by employing an index replacement mechanism and some other schemes perform embedding by adopting one of the possible ways during encoding each index when multiple ways are possible to encode the index. In the current research, two schemes are proposed based on the second mechanism. Outputted code of the proposed schemes is a legitimate STC/DTCS code and the conventional STC/DTCS decoder can decode it to the original VQ index table. The experimental results show that the proposed schemes are feasible and in comparison with some previous RDH schemes, the first one provides higher embedding capacity and the second one embeds a substantial amount of data while provides lower bit rate than most the previous schemes. In addition, the embedding-efficiency of both proposed schemes is higher than that of the previous schemes.

关键词： data encapsulation image coding vector quantisation tree codes decoding trees (mathematics) reversible data hiding scheme VQ image compression index coding vector quantisation image compression switching-tree coding dynamic tree-coding scheme VQ-based RDH schemes nonlegitimate codes index replacement mechanism legitimate STC-DTCS code VQ index table

来源：评论

学校读者我要写书评

暂无评论

Duality Codes and the Integrality Gap Bound for index coding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第11期60卷 7256-7268页

作者： Yu, Hao Neely, Michael J. Univ So Calif Dept Elect Engn Los Angeles CA 90089 USA

This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case, when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for nonplanar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between maximum distance separable codes. This paper illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations.

关键词： index coding integrality gap

来源：评论

学校读者我要写书评

暂无评论

Average Probability of Error for Single Uniprior index coding Over Binary-Input Continuous-Output Channels

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6297-6315页

作者： Mahesh, Anjana A. Rajput, Charul Rupa, Bobbadi Rajan, B. Sundar Samsung Res & Dev Inst Bengaluru 560037 India Aalto Univ Dept Math & Syst Anal Espoo 02150 Finland Mavenir Syst Pvt Ltd Bengaluru 560045 India Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India

Ong and Ho developed optimal linear index codes for single uniprior index coding problems (ICPs) by finding a spanning tree for each strongly connected component of their information-flow graphs, following which Thomas et al. considered the same class of ICPs over Rayleigh fading channels. They developed the min-max probability of error criterion for choosing an index code from the set of bandwidth-optimal linear index codes. Motivated by the above works, this paper deals with single uniprior ICPs over binary-input continuous-output channels. Minimizing the average probability of error is introduced as a criterion for further selection of index codes which is shown to be equivalent to minimizing the total number of transmissions used for decoding the message requests at all the receivers. An algorithm that generates a spanning tree with a lower value of this metric than the optimal star graph is also presented. A couple of lower bounds for the total number of transmissions, used by any optimal index code, are derived, and two classes of ICPs for which these bounds are tight are identified. An improvement of the proposed algorithm for information-flow graphs with bridges and a generalization of the improved algorithm for information-flow graphs obtainable as the union of strongly connected sub-graphs are presented, and some optimality results are derived.

关键词： indexes Codes Receivers Servers Encoding Decoding Noise measurement Broadcasting index coding probability of error spanning tree star graph

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：