Wiki
Clone wikisage_coding_project / Use_cases_on_benchmarking
This page summarises some use cases related to benchmarking and performance diagrams on codes and decoding. It aims at listing a few very detailed examples.
For now, it only contains a short description of some cases:
- Compare speed of decoding algortihms.
- Consider a GRS code over GF(101), whose length is in the interval [10, 100] (increasing by 10 at each step), dimension is
length/2
, evaluation points are chosen from 1 to n, no column-multipliers, I want to compare the speed of Gao decoder, Berlekamp-Welch decoder and Key-equation syndrome decoder. - Examples:
F = GF(101) report_BW = Benchmark(lambda t: (C = GRS(F.list()[:t], t/2), C.encoder(), C.decoder("BerlekampWelch"), StaticErrorRateChannel(C.ambient_space(), (C.minimum_distance() - 1)//2), range(10, 110, 10))) plot_BW = report_BW.plot_speed() report_Gao = Benchmark(lambda t: (C = GRS(F.list()[:t], t/2), C.encoder(), C.decoder("Gao"), StaticErrorRateChannel(C.ambient_space(), (C.minimum_distance() - 1)//2), range(10, 110, 10))) plot_Gao = report_Gao.plot_speed() report_Key = Benchmark(lambda t: (C = GRS(F.list()[:t], t/2), C.encoder(), C.decoder("KeyEquationSyndrome"), StaticErrorRateChannel(C.ambient_space(), (C.minimum_distance() - 1)//2), range(10, 110, 10))) plot_Key = report_Key.plot_speed() plot_final = plot_BW + plot_Gao + plot_Key
- Consider a GRS code over GF(101), whose length is in the interval [10, 100] (increasing by 10 at each step), dimension is
- Evaluate RoF on probabilistic decoders
- Consider a GRS code over GF(59), length 40, dimension 12, evaluation points are chosen from 1 to 40, no column multipliers. I want to check the RoF of Information Set decoding as we increase the number of errors (even beyond minimum distance).
- Examples:
C = codes.GeneralizedReedSolomonCode(GF(59).list()[1:41], 12 d = (C.minimum_distance()-1) //2 report = Bemchmark(lambda t: (C.encoder(), C.decoder("InformationSet", 2, t), StaticErrorRateChannel(C.ambient_space(), t), range(d, d+14)) report.plot_rate_of_failure()
- Considering given code and a given decoding algorithm with several input parameters (e.g. Guruswami-Sudan, power decoding), describe the behaviour of the decoder while changing its input (e.g. increase list-size parameter of Guruswami-Sudan beyond advised value for a given code).
- Compare decoding performances of Concatenated/Interleaved codes vs "Native" codes with the same [n, k].
- Consider a [42, 6] GRS code and a [42, 6] Concatenated code (inner code -> dual code of [7,3] Hamming code, outer code -> [6, 2] GRS code). Perform decoding using a burst-error channel and locating the burst in blocks. Compare the number of errors one is able on both codes.
- Later on: waterfall diagrams: SNR vs probability of failure.
Useful parameters
One might like to access to:
- the number of tests performed at each step (if it plots the average speed, on how many runs this average was computed?)
- the average rate of failure
- the average speed
Daniel's example
- consider using several RS code of contant rate and growing length decoded with Guruswami-Sudan, and various list sizes l given to the decoder
- one possible plot would be the standard waterfalls for each code and list size: word error rate y-axis, signal-to-noise-ratio on the x-axis
- one other relevant plot would to plot for each code the size of the returned list on the y-axis, for each code, with signal-to-noise-ratio on the x-axis
Another example, inspired by Johan's observation on AG codes
Since it may happen that more errors than what is predicted can often be corrected, so one may want to
- consider a given curve, a given length, and check the impact of the dimension on the phenomenon
- again standard waterfalls are required
- yet, also the percentage of failures is relevant to be plotted.
Features
Implemented features
- Being able to interrupt the tests and restart later.
- Everything must be saved: number of tests per step, words generated, code, timings, error-rate...
- Being able to vary the number of tests to perform from step to step.
- Semigroup behaviour: benchmarks can be added to combine their results (as plots).
- Benchmark should contain both the tests to run and the data got from the simulations.
- Data can be exported.
- Query the object on some aggregated statistics on the data.
- Some basics on plotting.
Features-to-be
- Having a real-time (-ish) saving mechanism.
- Support a behaviour like "Perform tests until my decoding failed
x
times". - Multi-threading.
- Custom data-saving.
Input
- Encoder, Decoder and Channel. Use
lambda
function to iterate on the object one wants to change throughout the simulation.
Updated