Constraint satisfaction through GBP-guided deliberate bit flipping

Mohsen Bahrami, Bane Vasić

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we consider the problem of transmitting binary messages over data-dependent two-dimensional channels. We propose a deliberate bit flipping coding scheme that removes channel harmful configurations prior to transmission. In this method, user messages are encoded with an error correction code, and therefore the number of bit flips should be kept small not to overburden the decoder. We formulate the problem of minimizing the number of bit flips as a binary constraint satisfaction problem, and devise a generalized belief propagation guided method to find approximate solutions. Applied to a data-dependent binary channel with the set of 2-D isolated bit configurations as its harmful configurations, we evaluated the performance of our proposed method in terms of uncorrectable bit-error rate.

Original languageEnglish (US)
Title of host publicationAlgebraic Informatics - 8th International Conference, CAI 2019, Proceedings
EditorsMiroslav Ćirić, Manfred Droste, Jean-Éric Pin
Number of pages12
ISBN (Print)9783030213626
StatePublished - 2019
Event8th International Conference on Algebraic Informatics, CAI 2019 - Niš, Serbia
Duration: Jun 30 2019Jul 4 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11545 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Conference on Algebraic Informatics, CAI 2019


  • Generalized belief propagation
  • Graphical models
  • Probabilistic inference

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Constraint satisfaction through GBP-guided deliberate bit flipping'. Together they form a unique fingerprint.

Cite this