Automatic Decoder Synthesis: Advancements in Communication and Cryptography

Cutting-edge progress in automatic decoder synthesis for communication and cryptography systems, presented in a comprehensive study covering motivation, prior work, preliminary notations, SAT solver algorithms, and experimental findings.

• Automatic Decoder
• Synthesis
• Communication
• Cryptography
• Algorithm

lamers_o Follow

Uploaded on Oct 06, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Towards Completely Automatic Decoder Synthesis Presented by Dec. 3, 2010

2. Outline Introduction Preliminary Main Algorithm Experimental Result Conclusion

3. Outline Introduction Preliminary Main Algorithm Experimental Result Conclusion

4. Introduction Motivation Data processing Communication, cryptography Encode-decode system Prior work Craig interpolation

5. Outline Introduction Preliminary Notation SAT Solver Craig Interpolation State Transition System Problem Statement Main Algorithm Experimental Result Conclusion

6. Preliminary Notation Boolean vector Cardinality Set of truth valuation

7. Preliminary SAT Solver For a Boolean vector and a Boolean function , SAT Solver asks whether That is whether is unsatisfiable.

8. Preliminary Craig interpolation refers to the common variables of and such that unsatisfiable

9. Preliminary State Transition System Initial states Transition relation Input variables Current-/Next-state variables Output variables

10. Tn T 1 T0 T1 Tp Preliminary T* 1 T*0 T*1 T*p T* n State Transition System Furthermore ? ? At time t T Duplication ? ? Duplication at time t

11. Preliminary State Transition System Dangling, recurrent and transition states dangling transition recurrent recurrent

12. Preliminary Problem Statement Streaming decoder Time-frame expansion of an encoder Finite observing window Prefix and postfix issue Care-state

13. Outline Introduction Preliminary Main Algorithm Decoder Existence Decoder Synthesis Disjunction on CNF Incremental SAT Experimental Result Conclusion

14. Decoder Existence(I)

15. Decoder Existence(II) the same state information, the same output equivalent constrain. ?? ???? ??? ?????? ???????? ?? ?????? ???????.

16. Decoder Existence(III) No more information obtain from adding new timeFrame ??????? ????? ? ?????.

17. Decoder Existence(IV) Decoder existence checking flow.

18. Decoder Synthesis T n T 1 T0 T1 Tp = = = = = T* n T* 1 T*0 T*1 T*p

19. Disjunction on CNF

20. Incremental SAT

21. Outline Introduction Preliminary Main Algorithm Experimental Result Existence Checking Decoder Synthesis Conclusion

22. Comparison on Decoder Generation time generate check aig size level

23. Compare: Decoder Existence Checking Time to check circuit without decoder

24. Comparison on Existence Checking and Decoder Generation

25. Outline Introduction Preliminary Main Algorithm Experimental Result Conclusion

26. Future Work

27. T n T 1 T0 T1 Tp = = = = = T* n T* 1 T*0 T*1 T*p

28. T n T 1 T0 T1 Tp = = = = = T* n T* 1 T*0 T*1 T*p

29. T n T 1 T0 T1 Tp T* n T* 1 T*0 T*1 T*p

30. T n T 1 T0 T1 Tp = = = = = T* n T* 1 T*0 T*1 T*p

31. ? ? T T ? ?