Channel coding plays a vital role in telecommunication. Low-Density Parity- Check (LDPC) codes are linear error-correcting codes. According to the 3rd Generation Partnership Project (3GPP) TS 38.212, LDPC is recommended for the Fifth-generation (5G) New Radio (NR) shared channels due to its high throughput, low latency, low decoding complexity and rate compatibility. LDPC encoding chain has been defined in 3GPP TS 38.212, but some details of LDPC encoding chain are still required to be explored in the MATLAB environment. For example, how to deal with the filler bits for encoding and decoding. However, as the reverse process of LDPC encoding, there is no information on LDPC decoding process for 5G NR shared channels in 3GPP TS 38.212. In this thesis project, LDPC encoding and decoding chains were thoughtfully developed with MATLAB programming based on 3GPP TS 38.212. Several LDPC decoding algorithms were implemented and optimized. The performance of LDPC algorithms was evaluated using block error rate (BLER) v.s. signal to noise ratio (SNR) and CPU time. Results show that the double diagonal structure-based encoding method is an efficient LDPC encoding algorithm for 5G NR. Layered Sum Product Algorithm (LSPA) and Layered Min-Sum Algorithm (LMSA) are more efficient than Sum Product Algorithm (SPA) and Min-Sum Algorithm (MSA). Layered Normalized Min-Sum Algorithm (LNMSA) with proper normalization factor and Layered Offset Min-Sum Algorithm (LOMSA) with good offset factor can optimize LMSA. The performance of LNMSA and LOMSA decoding depends more on code rate than transport block. / Kanalkodning spelar en viktig roll i telekommunikation. Paritetskontrollkoder med låg densitet (LDPC) är linjära felkorrigeringskoder. Enligt tredje generationens partnerskapsprojekt (3GPP) TS 38.212, LDPC rekommenderas för den femte generationens (5G) nya radio (NR) delade kanal på grund av dess höga genomströmning, låga latens, låga avkodningskomplexitet och hastighetskompatibilitet. LDPC kodningskedjan har definierats i 3GPP TS 38.212, men vissa detaljer i LDPC kodningskedjan krävs fortfarande för att utforskas i Matlabmiljön. Till exempel hur man hanterar fyllnadsbitar för kodning och avkodning. Men som den omvända processen för LDPC kodning finns det ingen information om LDPC avkodningsprocessen för 5G NR delade kanaler på 3GPP TS 38.212. I detta avhandlingsprojekt utvecklades LDPC-kodning och avkodningskedjor enligt 3GPP TS 38.212. Flera LDPC-avkodningsalgoritmer implementerades och optimerades. Prestandan för LDPC-algoritmer utvärderades med användning av blockfelshalt (BLER) v.s. signal / brusförhållande (SNR) och CPU-tid. Resultaten visar att den dubbla diagonala strukturbaserade kodningsmetoden är en effektiv LDPC kodningsalgoritm för 5G NR. Layered Sum Product Algorithm (LSPA) och Layered Min-Sum Algorithm (LMSA) är effektivare än Sum Product Algorithm (SPA) och Min-Sum Algorithm (MSA). Layered Normalized Min-Sum Algorithm (LNMSA) med rätt normaliseringsfaktor och Layered Offset Min-Sum Algorithm (LOMSA) med bra offsetfaktor kan optimera LMSA. Prestandan för LNMSA- och LOMSA-avkodning beror mer på kodhastighet än transportblock.

No description available.

No description available.

No description available.

Due to the widespread demands for efficient Propositional Satisfiability (SAT) solvers and its derivatives in Electronic Design Automation applications, methods to boost the performance of the SAT solver are highly desired. This dissertation aims to enhance the performance of SAT and related SAT solving problems. A hybrid solution to boost SAT solver performance is proposed as an initial attack in this dissertation, via an integration of local and DPLL-based search approaches. Next, a different hybrid strategy is attempted that takes advantage of the conflicts in the SAT search, which plays a critical role in modern SAT solvers. Usually a learned conflict-induced clause is added back to the clause database. Although conflict-induced clauses help to block a portion of the search space, they can also become a burden due to the added cost in memory consumption and Boolean Constraint Propagation (BCP). We thus propose a novel double-layer conflict-driven learning to store only those "primary" conflict clauses back into the clause database while keeping the other clauses as pseudo Boolean constraints. With this approach our experiments demonstrate that the approach can improve both in performance and memory consumption. This work opens the door on how to assess the usefulness of conflict induced clauses. Besides the aforementioned works about enhancing SAT solver performance and reducing memory cost, this dissertation also proposed a contributing work on the extended SAT problem solving. The current SAT solvers can provide an assignment for a satisfiable propositional formula. However, the capability for a SAT solver to return an "optimal" solution for a given objective function is severely lacking. MIN-ONE SAT is an optimization problem which requires the satisfying assignment with the minimal number of Ones, and it can be easily extended to minimize an arbitrary linear objective function. While some research has been conducted on MIN-ONE SAT, the existing algorithms do not scale very well on large formulas. This dissertation presents a novel approximation algorithm (RelaxSAT) for MIN-ONE SAT. RelaxSAT generates a set of constraints from the objective function to guide the search. The constraints are gradually relaxed to eliminate the conflicts with the original Boolean SAT formula until a solution is found. The experiments demonstrate that RelaxSAT is able to handle very large instances which cannot be solved by existing MIN-ONE algorithms; furthermore, RelaxSAT is able to obtain a very tight bound on the solution with one to two orders of magnitude speedup. Based on the proposed powerful MIN-ONE SAT algorithm, we built a MAX-SAT solver which achieved more than one order of magnitude speed up compared with the-state-of-art MAX-SAT solver. We also discuss a promising application of this MAX-SAT solver in formal verification. / Ph. D.

A Factor Graph (FG -- http://en.wikipedia.org/wiki/Factor_graph) is a structure used to find solutions to problems that can be represented as a Probabilistic Graphical Model (PGM). They consist of interconnected variable nodes and factor nodes, which iteratively compute and pass messages to each other. FGs can be applied to solve decoding of forward error correcting codes, Markov chains and Markov Random Fields, Kalman Filtering, Fourier Transforms, and even some games such as Sudoku. In this paper, a framework is presented for rapid prototyping of hardware implementations of FG-based applications. The FG developer specifies aspects of the application, such as graphical structure, factor computation, and message passing algorithm, and the framework returns a design. A system of Python scripts and Verilog Hardware Description Language templates together are used to generate the HDL source code for the application. The generated designs are vendor/platform agnostic, but currently target the Xilinx Virtex-6-based ML605. The framework has so far been primarily applied to construct Low Density Parity Check (LDPC) decoders. The characteristics of a large basket of generated LDPC decoders, including contemporary 802.11n decoders, have been examined as a verification of the system and as a demonstration of its capabilities. As a further demonstration, the framework has been applied to construct a Sudoku solver. / Master of Science

Cette étude présente un relevé et une analyse systématique des passages de la littérature rabbinique (Mishna – Tosefta – Talmud de Jérusalem – Talmud de Babylone – Midrashim) se rapportant à Jésus ou susceptibles de s'y rapporter. Les documents sont examinés, critiqués et confrontés à d'autres sources d'origine juive ou chrétienne (littérature judéo-hellénistique, apocryphes juifs, sources rabbiniques, Targumim, Toledot Yeshu – Nouveau Testament, Pères apostoliques, Père de l'église). L'enquête tente de répondre à plusieurs questions : - Quelle connaissance les rabbins avaient-ils exactement de Jésus ? - Quelle est la valeur historique de ces informations ? - Leur perception du personnage a-t-elle connu une évolution ? - Les scribes du Talmud consultaient-ils le texte écrit des évangiles ? La conclusion de cette thèse est que tous ces documents sont enracinés dans leur Sitz im leben. Ils attestent sans ambages – contra Peter Schäfer (Jesus in the Talmud, 2007) – que les rabbins n'avaient pas une connaissance directe des évangiles en tant que documents écrits. Cette étude montre également, concernant le Talmud de Babylone, que tous les passages se rapportant à Jésus appartiennent à la dernière couche éditoriale de ce corpus (VIIe-VIIIe siècle). / This study presents a survey and a systematic analysis of the passages of Talmudic literature (Mishna – Tosefta – Palestinian Talmud – Babylonian Talmud – Midrashim), relative to Jesus or are supposed to be. The documents are examined, criticized and confronted to other sources of Jewish or Christian origin (Hellenistic Jewish literature, Jewish Apocrypha, rabbinic sources, Targumim, Toledot Yeshu – New Testament, Apostolic Fathers, Church Fathers). The investigation tries to answer to several questions: - What did the rabbis exactly know about Jesus? - Has their information any historical value? - Has their perception undergone some evolution? - Did the rabbis of the Talmud have access to the Gospels as a written source? The conclusion of this thesis is that all these documents are rooted in their Sitz im leben. They obviously attest – contra Peter Schäfer (Jesus in the Talmud, 2007) – that the rabbis had no direct acquaintance with the Gospels as written documents. This study also shows, concerning the Babylonian Talmud, that all the passages relative to Jesus belong to the last editorial layer of this corpus (VIIe-VIIIe century).

Dans cette thèse, nous étudions un principe général de convexification permettant de traiter certainsproblèmes variationnels non convexes sur Rd. Grâce à ce principe nous pouvons mettre en oeuvre lespuissantes techniques de dualité et ramener de tels problèmes à des formulations de type primal–dualdans Rd+1, rendant ainsi efficace la recherche numérique de minima globaux. Une théorie de ladualité et des champs de calibration est reformulée dans le cas de fonctionnelles à croissance linéaire.Sous certaines hypothèses, cela nous permet de généraliser un principe d’exclusion découvert parVisintin dans les années 1990 et de réduire le problème initial à la minimisation d’une fonctionnelleconvexe sur Rd. Ce résultat s’applique notamment à une classe de problèmes à frontière libre oumulti-phasique donnant lieu à des tests numériques très convaincants au vu de la qualité des interfacesobtenues. Ensuite nous appliquons la théorie des calibrations à un problème classique de surfacesminimales avec frontière libre et établissons de nouveaux résultats de comparaison avec sa varianteoù la fonctionnelle des surfaces minimales est remplacée par la variation totale. Nous généralisonsla notion de calibrabilité introduite par Caselles-Chambolle et Al. et construisons explicitementune solution duale pour le problème associé à la seconde fonctionnelle en utilisant un potentiellocalement Lipschitzien lié à la distance au cut-locus. La dernière partie de la thèse est consacrée auxalgorithmes d’optimisation de type primal-dual pour la recherche de points selle, en introduisant denouvelles variantes plus efficaces en précision et temps calcul. Nous avons en particulier introduit unevariante semi-implicite de la méthode d’Arrow-Hurwicz qui permet de réduire le nombre d’itérationsnécessaires pour obtenir une qualité satisfaisante des interfaces. Enfin nous avons traité la nondifférentiabilité structurelle des Lagrangiens utilisés à l’aide d’une méthode géométrique de projectionsur l’épigraphe offrant ainsi une alternative aux méthodes classiques de régularisation. / In this thesis, we study a general principle of convexification to treat certain non convex variationalproblems in Rd. Thanks to this principle we are able to enforce the powerful duality techniques andbring back such problems to primal-dual formulations in Rd+1, thus making efficient the numericalsearch of a global minimizer. A theory of duality and calibration fields is reformulated in the caseof linear-growth functionals. Under suitable assumptions, this allows us to revisit and extend anexclusion principle discovered by Visintin in the 1990s and to reduce the original problem to theminimization of a convex functional in Rd. This result is then applied successfully to a class offree boundary or multiphase problems that we treat numerically obtaining very accurate interfaces.On the other hand we apply the theory of calibrations to a classical problem of minimal surfaceswith free boundary and establish new results related to the comparison with its variant where theminimal surfaces functional is replaced by the total variation. We generalize the notion of calibrabilityintroduced by Caselles-Chambolle and Al. and construct explicitly a dual solution for the problemassociated with the second functional by using a locally Lipschitzian potential related to the distanceto the cut-locus. The last part of the thesis is devoted to primal-dual optimization algorithms forthe search of saddle points, introducing new more efficient variants in precision and computationtime. In particular, we experiment a semi-implicit variant of the Arrow-Hurwicz method whichallows to reduce drastically the number of iterations necessary to obtain a sharp accuracy of theinterfaces. Eventually we tackle the structural non-differentiability of the Lagrangian arising fromour method by means of a geometric projection method on the epigraph, thus offering an alternativeto all classical regularization methods.

Dans cette thèse, les réseaux coopératifs sont étudiés sous cette hypothèse que la source est incertain par rapport le canal en opération. Dans le premier chapitre, des stratégies coopératives sont développées pour les canaux à relais simultanés (SRC) lesquelles se composent d'un ensemble de deux canaux à relais parmi lesquels le canal en opération est choisi. Cela est équivalent au canal de diffusion à relais (BRC). Les bornes sur la région de capacité de BRC général sont dérivées. Les résultats de capacité sont obtenus pour les cas particuliers du canal à relais simultané semi-dégradé et dégradé Gaussien. Dans le deuxième chapitre, le canal à relais composite est considéré où le canal est tiré aléatoirement d'un ensemble de la distribution conditionnelle. Le débit est fixé en dépit du canal actuel et la probabilité d'erreur (EP) asymptotique est caractérisée. Une nouvelle stratégie de codage sélectif (SCS) est introduit permettant aux relais de choisir -selon leur mesurage du canal - la meilleur schéma de codage entre Décoder-et-Transmettre (DF) et Comprimer-et-Transmettre (CF). Les théorèmes de codage de réseau bruit généralisées sont démontrés pour le cas de réseau unicast général où les relais utilisent soit DF soit CF. Dans le troisième chapitre, le spectre asymptotique de EP est introduit en tant que nouvelle mesure de performance pour réseaux composites. Il est démontré que chaque code avec le débit hors de la borne cut-set, abouti à EP égal à un et le spectre asymptotique de EP coïncide avec la probabilité d'outage pour les réseaux satisfaisant la converse forte.

Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants. / Network Calculus is a theory aiming at computing worst-case bounds on performances in communication networks. The network is usually modelled by a digraph : the servers are located on the nodes and the flows must follow path in the digraph. There are constraints on the trafic curves (how much data have been through a given point since the activation of the network) and on the service curves (how much work each server may provide). To derive bounds on the worst-case performances, as the backlog or the end-to-end delay, these envelopes are combined thanks to tropical algebra operators: min, +, convolution... This thesis focuses on Network Calculus algorithmics, that is how effective is this formalism. This work led us to compare various models in the litterature, and to show expressiveness equivalence between Real-Time Calculus and Network Calculus. Then, we suggested a new (min, +) operator to compute performances bounds in networks with agregated flows and we studied feed-forward networks under blind multiplexing. We showed the difficulty to compute these bounds, but we gave an heuristic, which is polynomial for interesting cases.