The Experts below are selected from a list of 16098 Experts worldwide ranked by ideXlab platform

Laura Poggiolini - One of the best experts on this subject based on the ideXlab platform.

Gianna Stefani - One of the best experts on this subject based on the ideXlab platform.

Guy Even - One of the best experts on this subject based on the ideXlab platform.

  • on decoding irregular tanner codes with Local Optimality guarantees
    IEEE Transactions on Information Theory, 2014
    Co-Authors: Nissim Halabi, Guy Even
    Abstract:

    We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the Local Optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora , Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of Local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that Local Optimality in this new characterization implies maximum-likelihood (ML) Optimality and LP Optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check Local codes (e.g., low-density and high-density parity-check codes). We prove that if a Locally optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a Locally optimal codeword. Because Local Optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new Local-Optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP decoding fails to decode the transmitted codeword decays doubly exponentially in the girth of the Tanner graph.

  • Local Optimality guarantees for optimal decoding based on paths
    International Symposium on Turbo Codes and Iterative Information Processing, 2012
    Co-Authors: Nissim Halabi, Guy Even
    Abstract:

    This paper presents a unified analysis framework that captures recent advances in the study of Local-Optimality characterizations for codes on graphs. These Local-Optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local-Optimality implies both maximum-likelihood (ML) Optimality and linear-programming (LP) decoding Optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique Locally-optimal codeword, if one exists. We demonstrate this proof technique by considering a definition of Local Optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length h. We apply the technique of Local Optimality to a family of Tanner codes. Inverse polynomial bounds in the code length are proved on the word error probability of LP-decoding for this family of Tanner codes.

  • linear programming decoding of tanner codes with Local Optimality certificates
    International Symposium on Information Theory, 2012
    Co-Authors: Nissim Halabi, Guy Even
    Abstract:

    Given a channel observation y and a codeword x, we are interested in a one-sided error test that answers the questions: is x optimal with respect to y? is it unique? A positive answer for such a test is called a certificate for the Optimality of a codeword. We present new certificates that are based on combinatorial characterization for Local-Optimality of a codeword in irregular Tanner codes. The certificate is based on weighted normalized trees in computation trees of the Tanner graph. These trees may have any finite height h (even greater than the girth of the Tanner graph). In addition, the degrees of Local-code nodes are not restricted to two (i.e., skinny trees). We prove that Local-Optimality in this new characterization implies ML-Optimality and LP-Optimality, and show that a certificate can be computed efficiently. We apply the new Local-Optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP-decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP-decoding fails decays doubly exponentially in the girth of the Tanner graph.

  • hierarchies of Local Optimality characterizations in decoding tanner codes
    International Symposium on Information Theory, 2012
    Co-Authors: Nissim Halabi, Guy Even
    Abstract:

    Recent developments in decoding Tanner codes with maximum-likelihood certificates are based on a sufficient condition called Local Optimality. We define hierarchies of Locally optimal codewords with respect to two parameters. One parameter is related to the minimum distance of the Local codes in Tanner codes. The second parameter is related to the finite number of iterations used in iterative decoding. We show that these hierarchies satisfy inclusion properties as these parameters are increased. In particular, this implies that a codeword that is decoded with a certificate using an iterative decoder after h iterations is decoded with a certificate after k·h iterations, for every integer k.

  • Local Optimality certificates for lp decoding of tanner codes
    arXiv: Information Theory, 2011
    Co-Authors: Nissim Halabi, Guy Even
    Abstract:

    We present a new combinatorial characterization for Local Optimality of a codeword in an irregular Tanner code. The main novelty in this characterization is that it is based on a linear combination of subtrees in the computation trees. These subtrees may have any degree in the Local code nodes and may have any height (even greater than the girth). We expect this new characterization to lead to improvements in bounds for successful decoding. We prove that Local Optimality in this new characterization implies ML-Optimality and LP-Optimality, as one would expect. Finally, we show that is possible to compute efficiently a certificate for the Local Optimality of a codeword given an LLR vector.

Tamer Basar - One of the best experts on this subject based on the ideXlab platform.

Xianfeng Zhao - One of the best experts on this subject based on the ideXlab platform.

  • a steganalytic approach to detect motion vector modification using near perfect estimation for Local Optimality
    IEEE Transactions on Information Forensics and Security, 2017
    Co-Authors: Hong Zhang, Yun Cao, Xianfeng Zhao
    Abstract:

    This paper presents a steganalytic approach against motion vector-based video steganography that does not depend on the detailed knowledge of embedding algorithms. In most state-of-the-art video coding standards, the motion vector is the result of block-based motion estimation using rate-distortion optimization. That is to say, each motion vector is Locally optimal in a rate-distortion sense, and any modification will inevitably shift the motion vector from Locally optimal to non-optimal. As a consequence, it is a very strong evidence of steganography if some motion vectors are found to be Locally non-optimal. Based on this fact, the core of our method is an estimator to check the Local Optimality of motion vectors in a rate-distortion sense. We try to recover the necessary information used for motion vector decision that is lost during lossy compression, based on which a 36-D feature set is formed for training and classification. To demonstrate the effectiveness of the proposed approach, experiments are carried out in different settings. The corresponding results show that our approach has a wide applicability even at low embedding strengths. Particularly, the problem of cover source mismatch is largely alleviated, which indicates that the proposed approach is suitable to be used in situations where a very limited priori knowledge is available.

  • motion vector based video steganography with preserved Local Optimality
    Multimedia Tools and Applications, 2016
    Co-Authors: Hong Zhang, Yun Cao, Xianfeng Zhao
    Abstract:

    Current motion vector based video steganography is unable to preserve the Local Optimality of modified motion vectors. Thus they are vulnerable to the attack of steganalysis. In this paper, we have proposed a novel method to guarantee the Local Optimality of modified motion vectors. To modify a motion vector, firstly designate a search area which consists of candidate motion vectors. Second, evaluate the Local Optimality of each motion vector in the search area to locate all Local optimum ones, from which finally select the one contributing least to video compression efficiency degradation as the modified motion vector. Highly undetectable motion vector based video steganography can be developed by combining the proposed method with steganographic codes and reasonable cost assignment. Comparative experimental results have demonstrated that video steganography based on the proposed method is capable of withstanding current best steganalysis while keeping the video compression performance.

  • a novel embedding distortion for motion vector based steganography considering motion characteristic Local Optimality and statistical distribution
    Information Hiding, 2016
    Co-Authors: Peipei Wang, Hong Zhang, Yun Cao, Xianfeng Zhao
    Abstract:

    This paper presents an effective motion vector (MV)-based steganography to cope with different steganalytic models. The main principle is to define a distortion scale expressing the multi-level embedding impact of MV modification. Three factors including motion characteristic of video content, MV's Local Optimality and statistical distribution are considered in distortion definition. For every embedding location, the contributions of three factors are dynamically adjusted according to MV's property. Based on the defined distortion function, two layered syndrome-trellis codes (STCs) are utilized to minimize the overall embedding impact in practical embedding implementation. Experimental results demonstrate that the proposed method achieves higher level of security compared with other existing MV-based approaches, especially for high quality videos.