Technical Program

Paper Detail

Paper Title Querying Policies Based on Sparse Matrices for Noisy 20 Questions
Paper IdentifierTH4.R7.1
Authors Qin Huang, Simeng Zheng, Yuanhan Ni, Zulin Wang, Shuai Wang, Beihang University, China
Session Topics in Coding Theory
Location Bièvre, Level 5
Session Time Thursday, 11 July, 16:40 - 18:00
Presentation Time Thursday, 11 July, 16:40 - 17:00
Manuscript  Click here to download the manuscript
Abstract This paper shows that the error probability of a querying policy for noisy 20 questions is upper bounded by the minimum Hamming distance of its querying matrix. Following this distance principle, sparse querying matrices with the row-column constraint are constructed for the scenarios, where only limited areas can be detected at each querying round. It demonstrates that the row-column constraint promises a large minimum distance to ensure low error probability of queries. Moreover, the proposed sparse matrices with random block coding provide unequal error-protection capability to further improve the querying accuracy under the scenarios of detecting half of the areas. Simulation results verify that the quantized mean squared errors of our proposed policies outperform those of the existing policies under the above scenarios.