add BP-OSD

[royess]

This PR includes an implementation of BP-OSD (belief propagation with ordered statistics post-processing).

Reference: Algorithm 1 in paper.

In my tests, the implementation to work well an provide better decoding accuracy than BP alone for some classical codes.

I think it is suitable to be considered a first PR.

Future TODOs: The performance is not optimized. Also, to use it for quantum codes, some adaptions need to be done along with the QuantumClifford side.

[codecov]

Codecov Report

Attention: Patch coverage is 97.36842% with 2 lines in your changes missing coverage. Please review.

Project coverage is 58.96%. Comparing base (b1827e1) to head (1570a2f).
Report is 2 commits behind head on main.

Files with missing lines	Patch %	Lines
src/decoders/belief_propagation_osd.jl	97.26%	2 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main      #22      +/-   ##
==========================================
+ Coverage   53.45%   58.96%   +5.51%     
==========================================
  Files          13       14       +1     
  Lines         507      580      +73     
==========================================
+ Hits          271      342      +71     
- Misses        236      238       +2     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[royess]

@Krastanov please help review this PR, thanks!

[Krastanov]

This looks good, thanks!

It seems there are two new JET warnings in your code. Could you please see whether you can address them:

 rep = ═════ 2 possible errors found ═════
┌  @ LDPCDecoders /home/runner/work/LDPCDecoders.jl/LDPCDecoders.jl/src/decoders/belief_propagation_osd.jl:12
│┌  @ LDPCDecoders /home/runner/work/LDPCDecoders.jl/LDPCDecoders.jl/src/decoders/belief_propagation_osd.jl:10
││┌  @ LDPCDecoders /home/runner/work/LDPCDecoders.jl/LDPCDecoders.jl/src/decoders/belief_propagation_osd.jl:11
│││┌  @ LDPCDecoders /home/runner/work/LDPCDecoders.jl/LDPCDecoders.jl/src/decoders/belief_propagation.jl:48
││││ no matching method found `size(::LDPCDecoders.BeliefPropagationDecoder)`: LDPCDecoders.size(H::LDPCDecoders.BeliefPropagationDecoder)
│││└────────────────────
┌ decode!(decoder::LDPCDecoders.BeliefPropagationOSDDecoder, syndrome::AbstractVector) @ LDPCDecoders /home/runner/work/LDPCDecoders.jl/LDPCDecoders.jl/src/decoders/belief_propagation_osd.jl:29
│┌ osd(H::BitMatrix, syndrome::AbstractVector, bp_err::Vector{Float64}, osd_order::Int64) @ LDPCDecoders /home/runner/work/LDPCDecoders.jl/LDPCDecoders.jl/src/decoders/belief_propagation_osd.jl:93
││┌ setindex!(A::BitVector, v::BitVector, I::Vector) @ Base ./abstractarray.jl:1413
│││┌ _setindex!(::IndexLinear, A::BitVector, v::BitVector, i::Int64) @ Base ./abstractarray.jl:1432
││││┌ setindex!(B::BitVector, x::BitVector, i::Int64) @ Base ./bitarray.jl:702
│││││ no matching method found `convert(::Type{Bool}, ::BitVector)`: convert(Base.Bool, x::BitVector)
││││└────────────────────

[Krastanov]

Besides the warnings, this is good to merge. We should also post an issue about improvements to it:

• more general H permitted in the constructor (not necessary in the struct itself)
• sparse H for better performance
• potentially just use the H defined in the BP decoder field?
• a lot of allocations to fix (we probably want to create a scratch space structure, like for the other decoders)

[Krastanov]

marking as "request changes"

[royess]

@Krastanov I have fixed the JET warnings. Please help me review the changes, thanks!